The solar industry in residential areas has been witnessing an astonishing growth worldwide. At the heart of this transformation, affecting the edge of the electricity grid, reside smart inverters (SIs). These IoT-enabled devices aim to introduce a certain degree of intelligence to conventional inverters by integrating various grid support capabilities (e.g., voltage and frequency control). However, with the remarkable automation of these devices come enormous security risks. Thus, rising rates of vulnerabilities have increased the necessity for designing resilient, auditable, and secure SIs’ firmware over the air (FOTA) amendment schemes suitable for this heterogeneous SIs-based ecosystem. In this regard, we propose leveraging blockchain as an innovative technology to guarantee these cybersecurity requirements. In this article, we present the design of a distributed FOTA scheme, namely, RASSIFAB, governing the process of amending SIs’ firmware within residential areas in an immutable and scalable manner. The scheme was implemented on a blockchain test network to assess its functionalities and performance. We also carried out a security evaluation to determine whether RASSIFAB is resistant to various identified threats. The obtained results confirm that the scheme is efficient and sound. They also indicate that RASSIFAB ensures reliable and authentic firmware amendments even with malicious insiders, differentiating our framework from the existing ones.

In PCNs, nodes that forward payments between a source and a receiver are paid a small fee if the payment is successful. The fee is a compensation for temporarily committing funds to the payment. However, payments may fail due to insufficient funds or attacks, often after considerable delays of up to several days, leaving a node without compensation. Furthermore, attackers can intentionally cause failed payments, e.g., to infer private information (like channel balances), without any cost in fees. In this paper, we first use extensive form games to formally characterize the conditions that lead to rational intermediaries refusing (or agreeing) to forward payments. An intermediary’s decision to forward or not depends on the probability of failure, which they approximate based on past experience. We then propose and analyze an alternative fee model that allows the sender to determine and pay a fraction of the fee to intermediaries in a non-refundable manner. A rational sender chooses the fraction such that the intermediaries’ utility for forwarding the payment exceeds their utility for not forwarding. Our simulation study, based on real-world Lightning snapshots, confirms that our novel mechanism can increase the probability of successful payments by 12% and decrease routing fees for senders by about 6% if all nodes behave rationally. Furthermore, previously cost-free probing attacks now require that the attacker pays 1500 satoshis for every 1 million satoshis inferred.

Web3 is emerging as the new Internet-interaction model that facilitates direct collaboration between strangers without a need for prior trust between network participants and without central authorities. However, one of its shortcomings is the lack of a defense mechanism against the ability of a single user to generate a surplus of identities, known as the Sybil attack. Web3 has a Sybil attack problem because it uses peer sampling to establish connections between users. We evaluate the promising but under-explored direction of Sybil avoidance using network latency measurements, according to which two identities with equal latencies are suspected to be operated from the same node, and thus are likely Sybils. Network latency measurements have two desirable properties: they are only malleable by attackers by adding latency, and they do not require any trust between network participants. Our basic SybilSys mechanism avoids Sybil attackers using only network latency measurements if attackers do not actively exploit their malleability. We present an enhanced version of SybilSys that protects against targeted attacks using a variant of the flow correlation attack, which we name TrafficJamTrigger. We show how the message flows of Round-Trip Time measurements can be used to expose attack patterns and we propose and evaluate six classifiers to recognize these patterns. Our experiments show, through both emulation and real-world deployment, that enhanced SybilSys can serve a fundamental role for Web3, effectively establishing connections to real users even in the face of networks consisting of 99% Sybils.

Lightning, the prevailing solution to Bitcoin’s scalability issue, uses onion routing to hide senders and recipients of payments. Yet, the path between the sender and the recipient along which payments are routed is selected such that it is short, cost efficient, and fast. The low degree of randomness in the path selection entails that anonymity sets are small. However, quantifying the anonymity provided by Lightning is challenging due to the existence of multiple implementations that differ with regard to the path selection algorithm and exist in parallel within the network. In this paper, we propose a general method allowing a local internal attacker to determine sender and recipient anonymity sets. Based on an in-depth code review of three Lightning implementations, we analyze how an adversary can predict the sender and the recipient of a multi-hop transaction. Our simulations indicate that only one adversarial node on a payment path uniquely identifies at least one of sender and recipient for around 70% of the transactions observed by the adversary. Moreover, multiple colluding attackers can almost always identify sender and receiver uniquely.

Existing digital identity management systems fail to deliver the desirable properties of control by the users of their own identity data, credibility of disclosed identity data, and network-level anonymity. The recently proposed Self-Sovereign Identity (SSI) approach promises to give users these properties. However, we argue that without addressing privacy at the network level, SSI systems cannot deliver on this promise. In this paper we present the design and analysis of our solution TCID, created in collaboration with the Dutch government. TCID is a system consisting of a set of components that together satisfy seven functional requirements to guarantee the desirable system properties. We show that the latency incurred by network-level anonymization in TCID is significantly larger than that of identity data disclosure protocols but is still low enough for practical situations. We conclude that current research on SSI is too narrowly focused on these data disclosure protocols.

Large data centers are currently the mainstream infrastructures for big data processing. As one of the most fundamental tasks in these environments, the efficient execution of distributed data operators (e.g., join and aggregation) are still challenging current data systems, and one of the key performance issues is network communication time. State-of-the-art methods trying to improve that problem focus on either application-layer data locality optimization to reduce network traffic or on network-layer data flow optimization to increase bandwidth utilization. However, the techniques in the two layers are totally independent from each other, and performance gains from a joint optimization perspective have not yet been explored. In this article, we propose a novel approach called NEAL (NEtwork-Aware Locality scheduling) to bridge this gap, and consequently to further reduce communication time for distributed big data operators. We present the detailed design and implementation of NEAL, and our experimental results demonstrate that NEAL always performs better than current approaches for different workloads and network bandwidth configurations.

The demand for additional performance due to the rapid increase in the size and importance of data-intensive applications has considerably elevated the complexity of computer architecture. In response, systems offer pre-determined behaviors based on heuristics and then expose a large number of configuration parameters for operators to adjust them to their particular infrastructure. Unfortunately, in practice this leads to a substantial manual tuning effort. In this work, we focus on one of the most impactful tuning decisions in big data systems: the number of executor threads. We first show the impact of I/O contention on the runtime of workloads and a simple static solution to reduce the number of threads for I/O-bound phases. We then present a more elaborate solution in the form of self-adaptive executors which are able to continuously monitor the underlying system resources and detect contentions. This enables the executors to tune their thread pool size dynamically at runtime in order to achieve the best performance. Our experimental results show that being adaptive can significantly reduce the execution time especially in I/O intensive applications such as Terasort and PageRank which see a 34% and 54% reduction in runtime.

Workflow schedulers often rely on task runtime estimates when making scheduling decisions, and they usually target the scheduling of a single workflow or batches of workflows. In contrast, in this paper, we evaluate the impact of the absence or limited accuracy of task runtime estimates on slowdown when scheduling complete workloads of workflows that arrive over time. We study a total of seven scheduling policies: four of these are popular existing policies for (batches of) workloads from the literature, including a simple backfilling policy which is not aware of task runtime estimates, two are novel workloadoriented policies, including one which targets fairness, and one is the well-known HEFT policy for a single workflow adapted to the online workload scenario. We simulate homogeneous and heterogeneous distributed systems to evaluate the performance of these policies under varying accuracy of task runtime estimates. Our results show that for high utilizations, the order in which workflows are processed is more important than the knowledge of correct task runtime estimates. Under low utilizations, all policies considered show good results, even a policy which does not use task runtime estimates. We also show that our Fair Workflow Prioritization (FWP) policy effectively decreases the variance of workflow slowdown and thus achieves fairness, and that the planbased scheduling policy derived from HEFT does not show much performance improvement while bringing extra complexity to the scheduling process.

When multiple data-processing frameworks with time-varying workloads are simultaneously present in a single cluster or data-center, an apparent goal is to have them experience equal performance, expressed in whatever performance metrics are applicable. In modern data-center environments, Two-Level Schedulers (TLSs) that leave the scheduling of individual jobs to the schedulers within the data-processing frameworks are typically used for managing the resources of data-processing frameworks. Two such TLSs with opposite designs are Mesos and Koala-F. Mesos employs fine-grained resource allocation and aims at Dominant Resource Fairness (DRF) among framework instances by offering resources to them for the duration of a single task. In contrast, Koala-F aims at performance fairness among framework instances by employing dynamic coarse-grained resource allocation of sets of complete nodes based on performance feedback from individual instances. The goal of this paper is to explore the trade-offs between these two TLS designs when trying to achieve performance balance among frameworks. We select Apache Spark as a representative of data-processing frameworks, and perform experiments on a modest-sized cluster, using jobs chosen from commonly used data-processing benchmarks. Our results reveal that achieving performance balance among framework instances is a challenge for both TLS designs, despite their opposite design choices. Moreover, we exhibit design flaws in the DRF allocation policy that prevent Mesos from achieving performance balance. Finally, to remedy these flaws, we propose a feedback controller for Mesos that dynamically adapts framework weights, as used in Weighted DRF (W-DRF), based on their performance.

Providing fault-tolerance is of major importance for data analytics frameworks such as Hadoop and Spark, which are typically deployed in large clusters that are known to experience high failures rates. Unexpected events such as compute node failures are in particular an important challenge for in-memory data analytics frameworks, as the widely adopted approach to deal with them is to recompute work already done. Recomputing lost work, however, requires allocation of extra resource to re-execute tasks, thus increasing the job runtimes. To address this problem, we design a checkpointing system called Panda that is tailored to the intrinsic characteristics of data analytics frameworks. In particular, Panda employs fine-grained checkpointing at the level of task outputs and dynamically identifies tasks that are worthwhile to be checkpointed rather than be recomputed. As has been abundantly shown, tasks of data analytics jobs may have very variable runtimes and output sizes. These properties form the basis of three checkpointing policies which we incorporate into Panda.

Efficient execution of distributed database operators such as joining and aggregating is critical for the performance of big data analytics. With the increase of the compute speedup of modern CPUs, reducing the network communication time of these operators in large systems is becoming increasingly important, and also challenging current techniques. Significant performance improvements have been achieved by using state-of-the-art methods, such as reducing network traffic designed in the data management domain, and data flow scheduling in the data communications domain. However, the proposed techniques in both fields just view each other as a black box, and performance gains from a co-optimization perspective have not yet been explored. In this paper, based on current research in coflow scheduling, we propose a novel Coflow-based Co-optimization Framework (CCF), which can co-optimize application-level data movement and network-level data communications for distributed operators, and consequently contribute to their performance in large distributed environments. We present the detailed design and implementation of CCF, and conduct an experimental evaluation of CCF using large-scale simulations on large data joins. Our results demonstrate that CCF can always perform faster than current approaches on network communications in large-scale distributed scenarios.

Simplifying the task of resource management and scheduling for customers, while still delivering complex Quality-of-Service (QoS), is key to cloud computing. Many autoscaling policies have been proposed in the past decade to decide on behalf of cloud customers when and how to provision resources to a cloud application utilizing cloud elasticity features. However, in prior work, when a new policy is proposed, it is seldom compared to the state-of-the-art, and is often compared only to static provisioning using a predefined QoS target. This reduces the ability of cloud customers and of cloud operators to choose and deploy an autoscaling policy. In our work, we conduct an experimental performance evaluation of autoscaling policies, using as application model workflows, a commonly used formalism for automating resource management for applications with well-defined yet complex structure. We present a detailed comparative study of general state-of-the-art autoscaling policies, along with two new workflow-specific policies. To understand the performance differences between the 7 policies, we conduct various forms of pairwise and group comparisons. We report both individual and aggregated metrics. Our results highlight the trade-offs between the suggested policies, and thus enable a better understanding of the current state-of-the-art.

Many large-scale data analytics infrastructures are employed for a wide variety of jobs, ranging from short interactive queries to large data analysis jobs that may take hours or even days to complete. As a consequence, data-processing frameworks like MapReduce may have workloads consisting of jobs with heavy-tailed processing requirements. With such workloads, short jobs may experience slowdowns that are an order of magnitude larger than large jobs do, while the users may expect slowdowns that are more in proportion with the job sizes. To address this problem of large job slowdown variability in MapReduce frameworks, we design a scheduling system called TYREX that is inspired by the well-known TAGS task assignment policy in distributed-server systems. In particular, TYREX partitions the resources of a MapReduce framework, allowing any job running in any partition to read data stored on any machine, imposes runtime limits in the partitions, and successively executes parts of jobs in a work-conserving way in these partitions until they can run to completion. We develop a statistical model for dynamically setting the runtime limits that achieves near optimal job slowdown performance, and we empirically evaluate TYREX on a cluster system with workloads consisting of both synthetic and real-world benchmarks. We find that TYREX cuts in half the job slowdown variability while preserving the median job slowdown when compared to state-of-the-art MapReduce schedulers such as FIFO and FAIR. Furthermore, TYREX reduces the job slowdown at the 95th percentile by more than 50% when compared to FIFO and by 20-40% when compared to FAIR.

Graph processing is increasingly used in a variety of domains, from engineering to logistics and from scientific computing to online gaming. To process graphs efficiently, GPU-enabled graph-processing systems such as TOTEM and Medusa exploit the GPU or the combined CPU+GPU capabilities of a single machine. Unlike scalable distributed CPU-based systems such as Pregel and GraphX, existing GPU-enabled systems are restricted to the resources of a single machine, including the limited amount of GPU memory, and thus cannot analyze the increasingly large-scale graphs we see in practice. To address this problem, we design and implement three families of distributed heterogeneous graph-processing systems that can use both the CPUs and GPUs of multiple machines. We further focus on graph partitioning, for which we compare existing graph-partitioning policies and a new policy specifically targeted at heterogeneity. We implement all our distributed heterogeneous systems based on the programming model of the single-machine TOTEM, to which we add (1) a new communication layer for CPUs and GPUs across multiple machines to support distributed graphs, and (2) a workload partitioning method that uses offline profiling to distribute the work on the CPUs and the GPUs. We conduct a comprehensive real-world performance evaluation for all three families. To ensure representative results, we select 3 typical algorithms and 5 datasets with different characteristics. Our results include algorithm run time, performance breakdown, scalability, graph partitioning time, and comparison with other graph-processing systems. They demonstrate the feasibility of distributed heterogeneous graph processing and show evidence of the high performance that can be achieved by combining CPUs and GPUs in a distributed environment.

Due to the diversity in the applications that run in clusters, many different application frameworks have been developed, such as MapReduce for data-intensive batch jobs and Spark for interactive data analytics. A framework is first deployed in a cluster, and then starts executing a large set of jobs that are submitted over time. When multiple such frameworks with time-varying resource demands are presentin a single cluster, static allocation of resources on a per-framework basis leads to low system utilization and resource fragmentation. In this paper, we present koala-f, a resource manager that dynamically provides resources to frameworks by employing a feedback loop to collecttheir possibly different performance metrics. Frameworks periodically -- not necessarily with the same frequency -- report the values of their performancemetrics to koala-f, which then either rebalances their resources individuallyagainst the idle-resource pool, or, when the latter is empty, rebalances their resources amongst them. We demonstrate the effectiveness of koala-f with experiments in a real system.

Due to the diversity in the applications that run in large distributed environments, many different application frameworks have been developed, such as MapReduce for data-intensive batch jobs and Spark for interactive data analytics. After initial deployment, a framework starts executing a large set of jobs that are submitted over time. When multiple such frameworks with time-varying resource demands are consolidated in a large distributed environment, static allocation of resources on a per-framework basis leads to low system utilization and to resource fragmentation. The goal of my PhD research is to improve the system utilization and framework performances in such consolidated environments by using dynamic resource allocation for efficient resource sharing among frameworks. My contribution towards this goal is a design and an implementation of a scalable resource manager that dynamically balances resources across set of multiple diverse frameworks in a large distributed environment based on resource requirements, system utilization or performance levels in the deployed frameworks.

Online gaming franchises such as World of Tanks, Defense of the Ancients, and StarCraft have attracted hundreds of millions of users who, apart from playing the game, also socialize with each other through gaming and viewing gamecasts. As a form of User Generated Content (UGC), gamecasts play an important role in user entertainment and gamer education. They deserve the attention of both industrial partners and the academic communities, corresponding to the large amount of revenue involved and the interesting research problems associated with UGC sites and social networks. Although previous work has put much effort into analyzing general UGC sites such as YouTube, relatively little is known about the gamecast sharing sites. In this work, we provide the first comprehensive study of gamecast sharing sites, including commercial streaming-based sites such as Amazon’s Twitch.tv and community-maintained replay-based sites such as WoTreplays. We collect and share a novel dataset on WoTreplays that includes more than 380,000 game replays, shared by more than 60,000 creators with more than 1.9 million gamers. Together with an earlier published dataset on Twitch.tv, we investigate basic characteristics of gamecast sharing sites, and we analyze the activities of their creators and spectators. Among our results, we find that (i) WoTreplays and Twitch.tv are both fast-consumed repositories, with millions of gamecasts being uploaded, viewed, and soon forgotten; (ii) both the gamecasts and the creators exhibit highly skewed popularity, with a significant heavy tail phenomenon; and (iii) the upload and download preferences of creators and spectators are different: while the creators emphasize their individual skills, the spectators appreciate team-wise tactics. Our findings provide important knowledge for infrastructure and service improvement, for example, in the design of proper resource allocation mechanisms that consider future gamecasting and in the tuning of incentive policies that further help player retention.

Graph processing is increasingly used in knowledge economies and in science, in advanced marketing, social networking, bioinformatics, etc. A number of graph-processing systems, including the GPU-enabled Medusa and Totem, have been developed recently. Understanding their performance is key to system selection, tuning, and improvement. Previous performance evaluation studies have been conducted for CPU-based graph-processing systems, such as Graph and GraphX. Unlike them, the performance of GPU-enabled systems is still not thoroughly evaluated and compared. To address this gap, we propose an empirical method for evaluating GPU-enabled graph-processing systems, which includes new performance metrics and a selection of new datasets and algorithms. By selecting 9 diverse graphs and 3 typical graph-processing algorithms, we conduct a comparative performance study of 3 GPU-enabled systems, Medusa, Totem, and MapGraph. We present the first comprehensive evaluation of GPU-enabled systems with results giving insight into raw processing power, performance breakdown into core components, scalability, and the impact on performance of system-specific optimization techniques and of the GPU generation. We present and discuss many findings that would benefit users and developers interested in GPU acceleration for graph processing.

Many fields of modern science require huge amounts of computation, and workflows are a very popular tool in e-Science since they allow to organize many small, simple tasks to solve big problems. They are used in astronomy, bioinformatics, machine learning, social network analysis, physics, and many other branches of science. Workflows are notoriously difficult to schedule, and the vast majority of research on workflow scheduling is concerned with scheduling single workflows with known runtimes. The goal of this PhDresearch is to bring more realism to the problem of workflow scheduling in actual systems. First, in real systems, multiple workflows may be contending for the available resources. Second, task runtime estimates are not always known, and task runtime estimates may be wrong. Third, workflows are usually not the only type of jobs submitted to a system, there may for instance also be parallel applications and bags-of-tasks. Accordingly, the purpose of this PhD research is to create and analyze policies for online scheduling of workloads of workflows with and without known task runtimes that also contain jobs of other types. We are in the process of simulating policies, and we will validate our results by means of an implementation and real-world experiments with the KOALA-Workflow processing system.

Workflows are important computational tools in many branches of science, and because of the dependencies among their tasks and their widely different characteristics, scheduling them is a difficult problem. Most research on scheduling workflows has focused on the offline problem of minimizing the make span of single workflows with known task runtimes. The problem of scheduling multiple workflows has been addressed either in an offline fashion, or still with the assumption of known task runtimes. In this paper, we study the problem of scheduling workloads consisting of an arrival stream of workflows without task runtime estimates. The resource requirements of a workflow can significantly fluctuate during its execution. Thus, we present four scheduling policies for workloads of workflows with as their main feature the extent to which they reserve processors to workflows to deal with these fluctuations. We perform simulations with realistic synthetic workloads and we show that any form of processor reservation only decreases the overall system performance and that a greedy backfilling-like policy performs best.

Data enters are at the core of a wide variety of daily ICT utilities, ranging from scientific computing to online gaming. Due to the scale of today's data enters, the failure of computing resources is a common occurrence that may disrupt the availability of ICT services, leading to revenue loss. Although many high availability (HA) techniques have been proposed to mask resource failures, datacenter users' -- who rent datacenter resources and use them to provide ICT utilities to a global population' -- still have limited management options for dynamically selecting and configuring HA techniques. In this work, we propose Availability-on-Demand (AoD), a mechanism consisting of an API that allows datacenter users to specify availability requirements which can dynamically change, and an availability-aware scheduler that dynamically manages computing resources based on user-specified requirements. The mechanism operates at the level of individual service instance, thus enabling fine-grained control of availability, for example during sudden requirement changes and periodic operations. Through realistic, trace-based simulations, we show that the AoD mechanism can achieve high availability with low cost. The AoD approach consumes about the same CPU hours but with higher availability than approaches which use HA techniques randomly. Moreover, comparing to an ideal approach which has perfect predictions about failures, it consumes 13% to 31% more CPU hours but achieves similar availability for critical parts of applications.

A well-known problem when executing data-intensive workloads with such frameworks as MapReduce is that small jobs with processing requirements counted in the minutes may suffer from the presence of huge jobs requiring hours or days of compute time, leading to a job slowdown distribution that is very variable and that is uneven across jobs of different sizes. Previous solutions to this problem for sequential or rigid jobs in single-server and distributed-server systems include priority-based FeedBack Queueing (FBQ), and Task Assignment by Guessing Sizes (TAGS), which kills and restarts from scratch on another server jobs that exceed the local time limit. In this paper, we derive four scheduling policies that are rightful descendants of existing size-based scheduling disciplines (among which FBQ and TAGS) with appropriate adaptations to data-intensive frameworks. The two main mechanisms employed by these policies are partitioning the resources of the datacenter, and isolating jobs with different size ranges. We evaluate these policies by means of realistic simulations of representative MapReduce workloads from Facebook and show that under the best of these policies, the vast majority of short jobs in MapReduce workloads experience close to ideal job slowdowns even under high system loads (in the range of 0.7-0.9) while the slowdown of the very large jobs is not prohibitive. We validate our simulations by means of experiments on a real multicluster system, and we find that the job slowdown performance results obtained with both match remarkably well.

Accounting mechanisms based on credit are used in peer-to-peer systems to track the contribution of peers to the community for the purpose of deterring freeriding and rewarding good behavior. Most often, peers earn credit for uploading files, but other activities might be rewarded in the future as well, such as making useful comments or reporting spam. Credit earned can be used for accessing new content, or for receiving preferential treatment in case of network congestion. We define credit mining as the activity performed by peers for the purpose of earning credit. In this paper, we design, implement, and evaluate a system for decentralized credit mining that maximizes the contribution of idle peers to the community by automatically uploading popular files. Building on previous theoretical insights into the economics of communities, we select autonomous algorithms for bandwidth investment as the basis of our credit mining system. Additionally, we describe our experience with important challenges arising from Internet deployment, that are frequently neglected in emulation, including duplicate content avoidance, spam prevention, and the cost of keeping peer information updated. Furthermore, we implement an archival mode of operation, which prevents the disappearance of old content from the community. We show the feasibility and usefulness of our credit mining system through measurements from our implementation on top of Tribler, an Internet-deployed peer-to-peer system.

Distributed SQL Query Engines (DSQEs) are increasingly used in variety of domains, but especially users in small companies with little expertise may face the challenge of selecting an appropriate engine for their specific applications. Although both industry and academia are attempting to come up with high level benchmarks, the performance of DSQEs has never been explored or compared in-depth. We propose an empirical method for evaluating the performance of DSQEs with representative metrics, datasets, and system configurations. We implement a micro-benchmarking suite of three classes of SQL queries for both a synthetic and a real world dataset and we report response time, resource utilization, and scalability. We use our micro-benchmarking suite to analyze and compare three state-of-the-art engines, viz. Shark, Impala, and Hive. We gain valuable insights for each engine and we present a comprehensive comparison of these DSQEs. We find that different query engines have widely varying performance: Hive is always being outperformed by the other engines, but whether Impala or Shark is the best performer highly depends on the query type.

Summary User interactions are indispensable for any online network to thrive, especially for BitTorrent‐like and Web real‐time communication‐based distributed online networks that rely on users' collective contributions instead of the help of central servers. User interactions provide fine‐grained information for many applications, such as security enhancement and cooperation promotion. To date, several schemes forestimating user interaction strengthin centralized online networks have been proposed. In contrast, we present design, deployment, and analysis of UISE for user interaction strength estimation in distributed online networks. Among the strong points of UISE is that it captures both direct and indirect user interactions, and that it scales with only partial information dissemination. We apply UISE to devise the first distributed scheme for online time estimation and we implement it into Tribler, a distributed online network for media and social applications like file sharing, streaming, and voting. We demonstrate the accuracy and the scalability of UISE with different information dissemination protocols and user behaviors using simulations, emulations, and a real‐world deployment. Copyright © 2015 John Wiley & Sons, Ltd.

Multiplayer Online Games (MOGs) like Defense of the Ancients and StarCraft II have attracted hundreds of millions of users who communicate, interact, and socialize with each other through gaming. In MOGs, rich social relationships emerge and can be used to improve gaming services such as match recommendation and game population retention, which are important for the user experience and the commercial value of the companies who run these MOGs. In this work, we focus on understanding social relationships in MOGs. We propose a graph model that is able to capture social relationships of a variety of types and strengths. We apply our model to real-world data collected from three MOGs that contain in total over ten years of behavioral history for millions of players and matches. We compare social relationships in MOGs across different game genres and with regular online social networks like Facebook. Taking match recommendation as an example application of our model, we propose SAMRA, a Socially Aware Match Recommendation Algorithm that takes social relationships into account. We show that our model not only improves the precision of traditional link prediction approaches, but also potentially helps players enjoy games to a higher extent.

Although Multi-Avatar Distributed Virtual Environments (MAVEs) such as Real-Time Strategy (RTS) games entertain daily hundreds of millions of online players, their current designs do not scale. For example, even popular RTS games such as the StarCraft series support in a single game instance only up to 16 players and only a few hundreds of avatars loosely controlled by these players, which is a consequence of the Event-Based Lockstep Simulation (EBLS) scalability mechanism they employ. Through empirical analysis, we show that a single Area of Interest (AoI), which is a scalability mechanism that is sufficient for single-avatar virtual environments (such as Role-Playing Games), also cannot meet the scalability demands of MAVEs. To enable scalable MAVEs, in this work we propose Area of Simulation (AoS), a new scalability mechanism, which combines and extends the mechanisms of AoI and EBLS. Unlike traditional AoI approaches, which employ only update-based operational models, our AoS mechanism uses both event-based and update-based operational models to manage not single, but multiple areas of interest. Unlike EBLS, which is traditionally used to synchronize the entire virtual world, our AoS mechanism synchronizes only selected areas of the virtual world. We further design an AoS-based architecture, which is able to use both our AoS and traditional AoI mechanisms simultaneously, dynamically trading-off consistency guarantees for scalability. We implement and deploy this architecture and we demonstrate that it can operate with an order of magnitude more avatars and a larger virtual world without exceeding the resource capacity of players' computers.

In this paper we present the scaling of BTWorld, our MapReduce-based approach to observing and analyzing the global BitTorrent network which we have been monitoring for the past 4 years. BTWorld currently provides a comprehensive and complex set of queries implemented in Pig Latin, with data dependencies between them, which translate to several MapReduce jobs that have a heavy-tailed distribution with respect to both execution time and input size characteristics. Processing BitTorrent data in excess of 1 TB with our BTWorld workflow required an in-depth analysis of the entire software stack and the design of a complete optimization cycle. We analyze our system from both theoretical and experimental perspectives and we show how we attained a 15 times larger scale of data processing than our previous results.

Companies, scientific communities, and individual scientists with varying requirements for their compute-intensive applications may want to use public Infrastructure-as-a-Service clouds to increase the capacity of the resources they have access to. To enable such access, resource managers that currently act as gateways to clusters may also do so for clouds, but for this they require new architectures and scheduling frameworks. In this paper, we present the design and implementation of KOALA-C, which is an extension of the KOALA multicluster scheduler to multicloud environments. KOALA-C enables uniform management across multicluster and multicloud environments by provisioning resources from both infrastructures and grouping them into clusters of resources called sites. KOALA-C incorporates a comprehensive list of policies for scheduling jobs across multiple (sets of) sites, including both traditional policies and two new policies inspired by the well-known TAGS task assignment policy in distributed-server systems. Finally, we evaluate KOALA-C through realistic simulations and real-world experiments, and show that the new architecture and in particular its new policies show promise in achieving good job slowdown with high resource utilization.

The design and tuning of networked virtual environments (NVEs), such as World of Warcraft (WoW), require understanding the in-NVE mobility characteristics of their citizens. Although many mobility-aware NVE systems already exist, their validation and further development have been hampered by the lack of public datasets and of comparison studies based on multiple datasets. To address these two issues, in this work we collect from WoW mobility traces for over 30,000 virtual citizens, and compare these traces with traces collected from Second Life (SL) where the environment is designed and changed significantly by the citizens themselves. Furthermore, motivated by the existence of numerous studies and models of networked real-world environments (NRE), we systematically compare the characteristics of two NVE and two NRE mobility traces. Our comparative study reveals that long-tail distributions characterize well various mobility characteristics, that the invisible boundary of human movement also appears for NVEs, and that area-visitation shows personal preferences. We also find several differences between NVE and NRE mobility characteristics.

Technical universities, especially in Europe, are facing an important challenge in attracting more diverse groups of students, and in keeping the students they attract motivated and engaged in the curriculum. We describe our experience with gamification, which we loosely define as a teaching technique that uses social gaming elements to deliver higher education. Over the past three years, we have applied gamification to undergraduate and graduate courses in a leading technical university in the Netherlands and in Europe. Ours is one of the first long-running attempts to show that gamification can be used to teach technically challenging courses. The two gamification-based courses, the first-year B.Sc. course Computer Organization and an M.Sc.-level course on the emerging technology of Cloud Computing, have been cumulatively followed by over 450 students and passed by over 75% of them, at the first attempt. We find that gamification is correlated with an increase in the percentage of passing students, and in the participation in voluntary activities and challenging assignments. Gamification seems to also foster interaction in the classroom and trigger students to pay more attention to the design of the course. We also observe very positive student assessments and volunteered testimonials, and a Teacher of the Year award.

Running multiple instances of the MapReduce framework concurrently in a multicluster system or datacenter enables data, failure, and version isolation, which is attractive for many organizations. It may also provide some form of performance isolation, but in order to achieve this in the face of time-varying workloads submitted to the MapReduce instances, a mechanism for dynamic resource (re-)allocations to those instances is required. In this paper, we present such a mechanism called Fawkes that attempts to balance the allocations to MapReduce instances so that they experience similar service levels. Fawkes proposes a new abstraction for deploying MapReduce instances on physical resources, the MR-cluster, which represents a set of resources that can grow and shrink, and that has a core on which MapReduce is installed with the usual data locality assumptions but that relaxes those assumptions for nodes outside the core. Fawkes dynamically grows and shrinks the active MR-clusters based on a family of weighting policies with weights derived from monitoring their operation.

BitTorrent (BT) plays an important role in Internet content distribution. Because public BTs suffer from the free-rider problem, Darknets are becoming increasingly popular, which use Sharing Ratio Enforcement to increase their efficiency. We crawled and traced 17 Darknets from September 2009 to February 2011, and obtained datasets about over 5 million torrents. We conducted a broad range of measurements, including traffic, sites, torrents, and users activities. We found that some of the features of Darknets are noticeably different from public BTs. The results of our study reflect both macroscopic and microscopic aspects of the overall ecosystem of BitTorrent Darknets.

Workload modeling and performance evaluation play crucial roles in the study of scheduling algorithms on large-scale parallel and distributed systems. An effective design of a scheduling algorithm for these systems requires experiments with hundreds of simulations to evaluate its performance. Since each simulation needs one workload as input, only real workloads with usually a limited availability are not sufficient, and so representative workload models are needed. Several studies have shown that realistic workload characteristics such as burstiness, bag-of-tasks, etc., cause significant performance impacts on scheduling. Therefore, we argue that realistic workload models should contain as many characteristics of real workloads as possible. In practice, researchers use unrealistic workloads in their scheduling evaluations because they lack models that can help generate realistic workloads. In this article, we analyze real parallel workloads to show the presence of important characteristics including long range dependence, periodicity and temporal burstiness of job arrivals, bag-of-tasks behavior, and correlation of runtime and number of processors. Then, we present a systematic approach to create a complete model that contains all of these characteristics. Validation of our model with real world data shows that it does not only capture the above characteristics, but also can fit marginal distributions well.

The commoditization of big data analytics, that is, the deployment, tuning, and future development of big data processing platforms such as MapReduce, relies on a thorough understanding of relevant use cases and workloads. In this work we propose BTWorld, a use case for time-based big data analytics that is representative for processing data collected periodically from a global-scale distributed system. BTWorld enables a data-driven approach to understanding the evolution of BitTorrent, a global file-sharing network that has over 100 million users and accounts for a third of today's upstream traffic. We describe for this use case the analyst questions and the structure of a multi-terabyte data set. We design a MapReduce-based logical workflow, which includes three levels of data dependency - inter-query, inter-job, and intra-job - and a query diversity that make the BTWorld use case challenging for today's big data processing tools; the workflow can be instantiated in various ways in the MapReduce stack. Last, we instantiate this complex workflow using Pig-Hadoop-HDFS and evaluate the use case empirically. Our MapReduce use case has challenging features: small (kilobytes) to large (250 MB) data sizes per observed item, excellent (10-6) and very poor (102) selectivity, and short (seconds) to long (hours) job duration.

Scalable by design to very large computing systems such as grids and clouds, MapReduce is currently a major big data processing paradigm. Nevertheless, existing performance models for MapReduce only comply with specific workloads that process a small fraction of the entire data set, thus failing to assess the capabilities of the MapReduce paradigm under heavy workloads that process exponentially increasing data volumes. The goal of my PhD is to build and analyze a scalable and dynamic big data processing system, including storage (distributed file system), execution engine (MapReduce), and query language (Pig). My contributions for the first two years of PhD research are the following: 1) the design and implementation of a resource management system part of a MapReduce-based processing system for deploying and resizing MapReduce clusters over multicluster systems, 2) the design and implementation of a benchmarking tool for the MapReduce processing system, and 3) the evaluation and modeling of MapReduce using workloads with very large data sets. Furthermore, based on the first two years research, we will optimize the MapReduce system to efficiently process terabytes of data.

Massively Multiplayer Online Games (MMOGs) are an important type of distributed applications and have millions of users. Traditionally, MMOGs are hosted on dedicated clusters, distributed globally. With the advent of cloud computing, MMOGs such as Zynga's are increasingly run on cloud resources, through the use of cloud technology and innovation. Massivizing MMOGs on clouds is the focus of my PhD research. My main contributions are: 1) analyzing and modeling various MMOG workloads, including those of social and traditional real-time games, 2) designing and implementing a cost-efficient and reliable cloud-based MMOG platform, 3) designing and implementing a scalable MMOG system which employs domain-specific scaling techniques to support the real time strategy games of the future, 4) experimental prototypes and tools to evaluate our proposed research via real-world experimentation and simulation, and applying our proposed research to a popular real-world application. In this article, I introduce my research progress and my future plans.

Spotify is a peer-assisted music streaming service that has gained worldwide popularity in the past few years. Until now, little has been published about user behavior in such services. In this paper, we study the user behavior in Spotify by analyzing a massive dataset collected between 2010 and 2011. Firstly, we investigate the system dynamics including session arrival patterns, playback arrival patterns, and daily variation of session length. Secondly, we analyze individual user behavior on both multiple and single devices. Our analysis reveals the favorite times of day for Spotify users. We also show the correlations between both the length and the downtime of successive user sessions on single devices. In particular, we conduct the first analysis of the device-switching behavior of a massive user base.

MapReduce, which is the de facto programming model for large-scale distributed data processing, and its most popular implementation Hadoop have enjoyed widespread adoption in industry during the past few years. Unfortunately, from a performance point of view getting the most out of Hadoop is still a big challenge due to the large number of configuration parameters. Currently these parameters are tuned manually by trial and error, which is ineffective due to the large parameter space and the complex interactions among the parameters. Even worse, the parameters have to be re-tuned for different MapReduce applications and clusters. To make the parameter tuning process more effective, in this paper we explore machine learning-based performance models that we use to auto-tune the configuration parameters. To this end, we first evaluate several machine learning models with diverse MapReduce applications and cluster configurations, and we show that support vector regression model (SVR) has good accuracy and is also computationally efficient. We further assess our auto-tuning approach, which uses the SVR performance model, against the Starfish auto tuner, which uses a cost-based performance model. Our findings reveal that our auto-tuning approach can provide comparable or in some cases better performance improvements than Starfish with a smaller number of parameters. Finally, we propose and discuss a complete and practical end-to-end auto-tuning flow that combines our machine learning-based performance models with smart search algorithms for the effective training of the models and the effective exploration of the parameter space.

Reputation systems are essential to establish trust and to provide incentives for cooperation among users in decentralized networks. In these systems, the most widely used algorithms for computing reputations are based on random walks. However, in decentralized networks where nodes have only a partial view of the system, random walk-based algorithms can be easily exploited by uncooperative and malicious nodes. Traditionally, a random walk only uses information about the adjacency of nodes, and ignores their structural and temporal properties. Nevertheless, the properties of nodes indicate their reliability, and so, random walks using much richer information about the nodes than simple adjacency may achieve higher robustness against malicious exploitations. In this paper, we introduce the properties of nodes that are indicative of their reliability, and we propose a scheme to integrate these properties into the traditional random walks. Particularly, we consider two common malicious exploitations of random walks in decentralized networks, uncooperative nodes and Sybil attacks, and we show that integrating node properties into random walks results in much more robust reputation systems. Our experimental evaluation in synthetic graphs and graphs derived from real-world networks covering a significant number of users, shows the effectiveness of the resulting biased random walks.

P2P communities that use credits to incentivize their members to contribute have emerged over the last few years. In particular, private BitTorrent communities keep track of the total upload and download of each member and impose a minimum threshold for their upload/download ratio, which is known as their sharing ratio. It has been shown that these private communities have significantly better download performance than public communities. However, this performance is based on oversupply, and it has also been shown that it is hard for users to maintain a good sharing ratio to avoid being expelled from the community. In this paper, we address this problem by introducing a speculative download mechanism to automatically manage user contribution in BitTorrent private communities. This mechanism, when integrated in a BitTorrent client, identifies the swarms that have the biggest upload potential, and automatically downloads and seeds them. In other words, it tries to invests the bandwidth of the user in a profitable way. In order to accurately asses the upload potential of swarms we analyze a private BitTorrent community and derive through multiple regression a predictor for the upload potential based on simple parameters accessible to each peer. The speculative download mechanism uses the predictor to build a cache of profitable swarms to which the peer can contribute. Our results show that 75 % of investment decisions result in an increase in upload bandwidth utilization, with a median 207 % return on investment.

SUMMARY As peer‐to‐peer (P2P) file‐sharing systems revolve around cooperation, the design of upload incentives has been one of the most important topics in P2P research for more than a decade. Several deployed systems, such as private BitTorrent communities, successfully manage to foster cooperation by banning peers when their sharing ratio becomes too low. Interestingly, recent measurements have shown that such systems tend to have an oversupply instead of an undersupply of bandwidth designers that have been obsessed with since the dawn of P2P. In such systems, the ‘selfish peer’ problem is finally solved, but a new problem has arisen: because peers have to keep up their sharing ratios, they now have to compete to upload. In this paper, we explore this new problem and show how even highly cooperative peers might in the end not survive the upload competition. On the basis of recent measurements of over half a million peers in private P2P communities, we propose and analyze several algorithms for uploader selection under oversupply. Our algorithms enable sustained sharing ratio enforcement and are easy to implement in both existing and new systems. Overall, we offer an important design consideration for the new generation of P2P systems in which selfishness is no longer an issue. Copyright © 2012 John Wiley & Sons, Ltd.

Many peer-to-peer communities, including private BitTorrent communities that serve hundreds of thousands of users, utilize credit-based or sharing ratio enforcement schemes to incentivize their members to contribute. In this paper, we analyze the performance of such communities from both the system-level and the user-level perspectives. We show that both credit-based and sharing ratio enforcement policies can lead to system-wide "crunches" or "crashes," where the system seizes completely due to too little or too much credit, respectively. We present a theoretical model that identifies the conditions that lead to these system pathologies and we design an adaptive credit system that automatically adjusts credit policies to maintain sustainability. Given private communities that are sustainable, it has been demonstrated that they are greatly oversupplied in terms of excessively high seeder-to-leecher ratios. We further analyze the user-level performance by studying the effects of oversupply. We show that although achieving an increase in the average downloading speed, the phenomenon of oversupply has three undesired effects: long seeding times, low upload capacity utilizations, and an unfair playing field for late entrants into swarms. To alleviate these problems, we propose four different strategies, which have been inspired by ideas in social sciences and economics. We evaluate these strategies through simulations and demonstrate their positive effects.

Due to the possibility of cheap identity creation, decentralized online reputation mechanisms are susceptible to sybil attacks. Barter Cast is a reputation mechanism used in the Internet-deployed Tribler file-sharing client. In this paper we study the opportunities for sybil attacks in Barter Cast and we devise a method for making Barter Cast sybil resilient, which is incorporated in a protocol called Sybil Res. Like in Barter Cast, in Sybil Res each peer maintains a local subjective weighted directed graph reflecting data transfer actions in Tribler, from which it computes the reputations of other peers using a flow based algorithm taking the edge weights as flows. In Sybil Res, after an upload action, the uploading peer discounts the weights of the edges on the paths from the down loader to itself. As a consequence, due to the way reputations are computed, the reputation of a peer performing a sybil attack decreases fast. To mitigate the negative impact of edge weight discounting on the reputations of honest peers, after a download action, the downloading peer increases the weights of the edges on the paths from the up loader to itself. We demonstrate that Sybil Res is effective in practice by means of trace-driven simulations using data collected from the Tribler network. The results show that Sybil Res effectively marginalizes attackers while having a minimal effect on the reputations of honest peers.

Video distribution is nowadays the dominant source of Internet traffic, and recent studies show that it is expected to reach 90% of the global consumer traffic by the end of 2015. Peer-to-peer assisted solutions have been adopted by many content providers with the aim of improving the scalability and reliability of their distribution network. While many solutions have been proposed, virtually all of them are at the overlay level, and so rely on the standard functionality of the transport layer. The Peer-to-Peer Streaming Protocol workgroup of the IETF has adopted the Libswift transport-layer protocol that is targeted at P2P traffic. In this paper we describe the design features and a first implementation of the Libswift protocol, and a piece-picking protocol that uses the transport features of Libswift in an essential way. We investigate its performance on both high-end and power-constrained low-end devices, comparing it to the state-of-the-art in P2P protocols.

Recently, utility Grids have emerged as a new model of service provisioning in heterogeneous distributed systems. In this model, users negotiate with service providers on their required Quality of Service and on the corresponding price to reach a Service Level Agreement. One of the most challenging problems in utility Grids is workflow scheduling, i.e., the problem of satisfying the QoS of the users as well as minimizing the cost of workflow execution. In this paper, we propose a new QoS-based workflow scheduling algorithm based on a novel concept called Partial Critical Paths (PCP), that tries to minimize the cost of workflow execution while meeting a user-defined deadline. The PCP algorithm has two phases: in the deadline distribution phase it recursively assigns subdeadlines to the tasks on the partial critical paths ending at previously assigned tasks, and in the planning phase it assigns the cheapest service to each task while meeting its subdeadline. The simulation results show that the performance of the PCP algorithm is very promising.

Cloud computing is an emerging infrastructure paradigm that promises to eliminate the need for companies to maintain expensive computing hardware. Through the use of virtualization and resource time-sharing, clouds address with a single set of physical resources a large user base with diverse needs. Thus, clouds have the potential to provide their owners the benefits of an economy of scale and, at the same time, become an alternative for both the industry and the scientific community to self-owned clusters, grids, and parallel production environments. For this potential to become reality, the first generation of commercial clouds need to be proven to be dependable. In this work we analyze the dependability of cloud services. Towards this end, we analyze long-term performance traces from Amazon Web Services and Google App Engine, currently two of the largest commercial clouds in production. We find that the performance of about half of the cloud services we investigate exhibits yearly and daily patterns, but also that most services have periods of especially stable performance. Last, through trace-based simulation we assess the impact of the variability observed for the studied cloud services on three large-scale applications, job execution in scientific computing, virtual goods trading in social networks, and state management in social gaming. We show that the impact of performance variability depends on the application, and give evidence that performance variability can be an important factor in cloud provider selection.

Enhancing reciprocity has been one of the primary motivations for the design of incentive policies in BitTorrent-like P2P systems. Reciprocity implies that peers need to contribute their bandwidth to other peers if they want to receive bandwidth in return. However, the over-provisioning that characterizes today's BitTorrent communities and the development of many next-generation P2P systems with real-time constraints (e.g., for live and on-demand streaming) suggest that more effort can be devoted to reducing the inequity (i.e., the difference of service received) among peers, rather than only enhancing reciprocity. Inspired by this observation, in this work we analyze in detail several incentive mechanisms that are used in BitTorrent systems, and explore several strategies that influence the balance between reciprocity and equity. Our study shows that (i) reducing inequity leads to a better overall system performance, and (ii) the behavior of seeders (i.e., peers that hold a complete copy of the file and upload it for free) influences whether reciprocity is enhanced or inequity reduced.

Interactive perception applications, such as gesture recognition and vision-based user interfaces, process high-data rate streams with compute intensive computer vision and machine learning algorithms. These applications can be represented as data flow graphs comprising several processing stages. Such applications require low latency to be interactive so that the results are immediately available to the user. To achieve low latency, we exploit the inherent coarse grained task and data parallelism of these applications by running them on clusters of machines. This paper addresses an important problem that arises: how to place the stages of these applications on machines to minimize the latency, and in particular, how to adjust an existing schedule in response to changes in the operating conditions (perturbations) while minimizing the disruption in the existing placement (churn). To this end, we propose four incremental placement heuristics which use the HEFT scheduling algorithm as their primary building block. Through simulations and experiments on a real implementation, using diverse workloads and a range of perturbation scenarios, we demonstrate that dynamic adjustment of the schedule can improve latency by as much as 36%, while producing little churn.

During the last decade of P2P research a lot of attention has been given to incentive mechanisms. While centralized incentive mechanisms are straightforward in their design, a long term challenge has been to create a decentralized incentive mechanism that can be used to effectively induce cooperation and reduce freeriding. While there have been many proposals of such mechanisms based on the spreading of reputation information, little attention has been given to the theoretical limitations of such designs. In this paper, we present a high level model of reputation-based incentive mechanisms. We derive upper bounds on the effectiveness of such mechanisms, especially with respect to the performance under behavioral change and population turnover. Moreover, we assess the effectiveness of a reputation overlay in BitTorrent, and show that while its tit-for-tat reciprocity algorithm provides incentives for uploading on the short term, it reduces the benefits of an integrated long term incentive mechanism. All in all, we offer important insights for the design of future incentive systems.

The volume of Internet video is growing, and is expected to exceed 57 percent of global consumer Internet traffic by 2014. Peer-to-Peer technology can help delivering this massive volume of traffic in a cost-efficient, scalable, and reliable manner. However, single bit rate streaming is not sufficient given today's device and network connection diversity. A possible solution to this problem is provided by layered coding techniques, such as Scalable Video Coding, which allow addressing this diversity by providing content in various qualities within a single bit stream. In this paper we propose a new self-adapting piece-picking algorithm for downloading layered video streams, called Deftpack. Our algorithm significantly reduces the number of stalls, minimises the frequency of quality changes during playback, and maximizes the effective usage of the available bandwidth. Deftpack is the first algorithm that is specifically crafted to take all these three quality dimensions into account simultaneously, thus increasing the overall quality of experience. Additionally, Deftpack can be integrated into Bit torrent-based P2P systems and so has the chance of large-scale deployment. Our results from realistic swarm simulations show that Deftpack significantly outperforms previously proposed algorithms for retrieving layered content when all three quality dimensions are taken into account.

A considerable body of research shows that Bit-Torrent provides very efficient resource allocation inside single swarms. Many BitTorrent clients also allow users to participate in multiple swarms simultaneously, and implement inter-swarm resource-allocation mechanisms that are used by millions of people. However, resource allocation across multiple swarms in BitTorrent has received much less attention. In this paper, we investigate whether currently prevalent inter-swarm resource allocation mechanisms perform acceptably or call for improvements. We use data from two BitTorrent communities and present results from trace-based simulations. Two use-cases for allocation mechanisms drive our evaluation: (1) file-sharing communities, whose objective is maximizing throughput, and (2) video-streaming communities, whose objective is maximizing the number of users receiving sufficient resources for uninterrupted streaming. To put the results from the analyzed mechanisms into perspective, we devise theoretical efficiency bounds for inter-swarm resource allocation, for which we map the resource allocation problem to a graph-theoretical flow network problem. In this formalism, the goal of the file-sharing use-case, throughput maximization, is equivalent to maximizing the flow in the network. The goal of the video-streaming use-case translates into finding a max-min fair allocation for BitTorrent downloading sessions, a problem for which we devise a new algorithm.

Many private BitTorrent communities employ Sharing Ratio Enforcement (SRE) schemes to incentivize users to contribute their upload resources. It has been demonstrated that communities that use SRE are greatly oversupplied, i.e., they have much higher seeder-to-leecher ratios than communities in which SRE is not employed. The first order effect of oversupply under SRE is a positive increase in the average downloading speed. However, users are forced to seed for extremely long times to maintain adequate sharing ratios to be able to start new downloads. In this paper, we propose a fluid model to study the effects of oversupply under SRE, which predicts the average downloading speed, the average seeding time, and the average upload capacity utilization for users in communities that employ SRE. We notice that the phenomenon of oversupply has two undesired negative effects: a) Peers are forced to seed for long times, even though their seeding efforts are often not very productive (in terms of low upload capacity utilization); and b) SRE discriminates against peers with low bandwidth capacities and forces them to seed for longer durations than peers with high capacities. To alleviate these problems, we propose four different strategies for SRE, which have been inspired by ideas in social sciences and economics. We evaluate these strategies through simulations. Our results indicate that these new strategies release users from needlessly long seeding durations, while also being fair towards peers with low capacities and maintaining high system-wide downloading speeds.

Flashcrowds - sudden surges of user arrivals - do occur in BitTorrent, and they can lead to severe service deprivation. However, very little is known about their occurrence patterns and their characteristics in real-world deployments, and many basic questions about BitTorrent flashcrowds, such as How often do they occur? and How long do they last?, remain unanswered. In this paper, we address these questions by studying three datasets that cover millions of swarms from two of the largest BitTorrent trackers. We first propose a model for BitTorrent flashcrowds and a procedure for identifying, analyzing, and modeling BitTorrent flashcrowds. Then we evaluate quantitatively the impact of flashcrowds on BitTorrent users, and we develop an algorithm that identifies BitTorrent flashcrowds. Finally, we study statistically the properties of BitTorrent flashcrowds identified from our datasets, such as their arrival time, duration, and magnitude, and we investigate the relationship between flashcrowds and swarm growth, and the arrival rate of flashcrowds in BitTorrent trackers. In particular, we find that BitTorrent flashcrowds only occur in very small fractions (0.3-2%) of the swarms but that they can affect over ten million users.

Cloud computing is an emerging commercial infrastructure paradigm that promises to eliminate the need for maintaining expensive computing facilities by companies and institutes alike. Through the use of virtualization and resource time sharing, clouds serve with a single set of physical resources a large user base with different needs. Thus, clouds have the potential to provide to their owners the benefits of an economy of scale and, at the same time, become an alternative for scientists to clusters, grids, and parallel production environments. However, the current commercial clouds have been built to support web and small database workloads, which are very different from typical scientific computing workloads. Moreover, the use of virtualization and resource time sharing may introduce significant performance penalties for the demanding scientific computing workloads. In this work, we analyze the performance of cloud computing services for scientific computing workloads. We quantify the presence in real scientific computing workloads of Many-Task Computing (MTC) users, that is, of users who employ loosely coupled applications comprising many tasks to achieve their scientific goals. Then, we perform an empirical evaluation of the performance of four commercial cloud computing services including Amazon EC2, which is currently the largest commercial cloud. Last, we compare through trace-based simulation the performance characteristics and cost models of clouds and other scientific computing platforms, for general and MTC-based scientific computing workloads. Our results indicate that the current clouds need an order of magnitude in performance improvement to be useful to the scientific community, and show which improvements should be considered first to address this discrepancy between offer and demand.

With the increasing functionality and complexity of distributed systems, resource failures are inevitable. While numerous models and algorithms for dealing with failures exist, the lack of public trace data sets and tools has prevented meaningful comparisons. To facilitate the design, validation, and comparison of fault-tolerant models and algorithms, we have created the Failure Trace Archive (FTA) as an online public repository of availability traces taken from diverse parallel and distributed systems. Our main contributions in this study are the following. First, we describe the design of the archive, in particular the rationale of the standard FTA format, and the design of a toolbox that facilitates automated analysis of trace data sets. Second, applying the toolbox, we present a uniform comparative analysis with statistics and models of failures in nine distributed systems. Third, we show how different interpretations of these data sets can result in different conclusions. This emphasizes the critical need for the public availability of trace data and methods for their analysis.

Performance evaluation is a significant step in the study of scheduling algorithms in large-scale parallel systems ranging from supercomputers to clusters and grids. One of the key factors that have a strong effect on the evaluation results is the workloads (or traces) used in experiments. In practice, several researchers use unrealistic synthetic workloads in their scheduling evaluations because they lack models that can help generate realistic synthetic workloads. In this paper we propose a full model to capture the following characteristics of real parallel system workloads: 1) long range dependence in the job arrival process, 2) temporal and spatial burstiness, 3) bag-oftasks behaviour, and 4) correlation between the runtime and the number of processors. Validation of our model with real traces shows that our model not only captures the above characteristics but also fits the marginal distributions well. In addition, we also present an approach to quantify burstiness in a job arrival process (temporal) as well as burstiness in the load of a trace (spatial).

Grid users may experience inconsistent performance due to specific characteristics of grids, such as fluctuating workloads, high failure rates, and high resource heterogeneity. Although extensive research has been done in grids, providing consistent performance remains largely an unsolved problem. In this study we use overdimensioning, a simple but cost-ineffective solution, to solve the performance inconsistency problem in grids. To this end, we propose several overdimensioning strategies, and we evaluate these strategies through simulations with workloads consisting of Bag-of-Tasks. We find that although overdimensioning is a simple solution, it is a viable solution to provide consistent performance in grids.

Scientists increasingly rely on the execution of workflows in grids to obtain results from complex mixtures of applications. However, the inherently dynamic nature of grid workflow scheduling, stemming from the unavailability of scheduling information and from resource contention among the (multiple) workflows and the non-workflow system load, may lead to poor or unpredictable performance. In this paper we present a comprehensive and realistic investigation of the performance of a wide range of dynamic workflow scheduling policies in multicluster grids. We first introduce a taxonomy of grid workflow scheduling policies that is based on the amount of dynamic information used in the scheduling process, and map to this taxonomy seven such policies across the full spectrum of information use. Then, we analyze the performance of these scheduling policies through simulations and experiments in a real multicluster grid. We find that there is no single grid workflow scheduling policy with good performance across all the investigated scenarios. We also find from our real system experiments that with demanding workloads, the limitations of the head-nodes of the grid clusters may lead to performance loss not expected from the simulation results. We show that task throttling, that is, limiting the per-workflow number of tasks dispatched to the system, prevents the head-nodes from becoming overloaded while largely preserving performance, at least for communication-intensive workflows. 1.

Most P2P systems that have some kind of incentive mechanism reward peers according to their contribution, i.e. total bandwidth offered to the system. Due to the disparity in bandwidth capacity between P2P users on the Internet, the common effect of such mechanisms is that the fastest peers reap the highest benefits. We take a different approach and study how to incentivize cooperation in P2P systems based on effort, i.e. contribution relative to capacity. We make the following contributions: 1) we argue that contribution-based incentive schemes in P2P systems unnecessarily disfavor slow peers and decrease overall system performance; 2) we advocate the use of principles from an alternative economic vision, Participatory Economics (Parecon), to inspire systems to be fair and to ensure maximization of the social welfare while being efficient at the same time, and 3) we present the results of simulations in which we apply principles from Parecon to two popular real life systems: a) the popular file sharing BitTorrent protocol; b) a generic credit based sharing ratio enforcement scheme. Our approach yields a higher system performance and fairness and offers new insights into P2P incentive design.

Superpeer architectures exploit the heterogeneity of nodes in a peer-to-peer (P2P) network by assigning additional responsibilities to higher capacity nodes. In the design of a superpeer network for file sharing, several issues have to be addressed: how client peers are related to superpeers, how superpeers locate files, how the load is balanced among the superpeers, and how the system deals with node failures. In this paper, we introduce a self-organizing superpeer network architecture (SOSPNet) that solves these issues in a fully decentralized manner. SOSPNet maintains a superpeer network topology that reflects the semantic similarity of peers sharing content interests. Superpeers maintain semantic caches of pointers to files, which are requested by peers with similar interests. Client peers, on the other hand, dynamically select superpeers offering the best search performance. We show how this simple approach can be employed not only to optimize searching, but also to solve generally difficult problems encountered in P2P architectures such as load balancing and fault tolerance. We evaluate SOSPNet using a model of the semantic structure derived from eight-month traces of two large file-sharing communities. The obtained results indicate that SOSPNet achieves close-to-optimal file search performance, quickly adjusts to changes in the environment (node joins and leaves), survives even catastrophic node failures, and efficiently distributes the system load taking into account superpeer capacities.

In multicluster grid systems, parallel applications may benefit from processor coallocation, that is, the simultaneous allocation of processors in multiple clusters. Although coallocation allows the allocation of more processors than available in a single cluster, it may severely increase the execution time of applications due to the relatively slow wide-area communication. The aim of this paper is to investigate the benefit of coallocation in multicluster grid systems, despite this drawback. To this end, we have conducted experiments in a real multicluster grid environment, as well as in a simulated environment, and we evaluate the performance of coallocation for various applications that range from computation-intensive to communication-intensive and for various system load settings. In addition, we compare the performance of scheduling policies that are specifically designed for coallocation. We demonstrate that considering latency in the resource selection phase improves the performance of coallocation, especially for communication-intensive parallel applications.

The use of today's multicluster grids exhibits periods of submission bursts with periods of normal use and even of idleness. To avoid resource contention, many users employ observational scheduling, that is, they postpone the submission of relatively low-priority jobs until a cluster becomes (largely) idle. However, observational scheduling leads to resource contention when several such users crowd the same idle cluster. Moreover, this job execution model either delays the execution of more important jobs, or requires extensive administrative support for job and user priorities. Instead, in this work we investigate the use of cycle scavenging to run jobs on grid resources politely yet efficiently, and with an acceptable administrative cost. We design a two-level cycle scavenging scheduling architecture that runs unobtrusively alongside regular grid scheduling. We equip this scheduler with two novel cycle scavenging scheduling policies that enforce fair resource sharing among competing cycle scavenging users. We show through experiments with real and synthetic applications in a real multicluster grid that the proposed architecture can execute jobs politely yet efficiently.

Cloud computing has emerged as a new technology that provides large amounts of computing and data storage capacity to its users with a promise of increased scalability, high availability, and reduced administration and maintenance costs. As the use of cloud computing environments increases, it becomes crucial to understand the performance of these environments. So, it is of great importance to assess the performance of computing clouds in terms of various metrics, such as the overhead of acquiring and releasing the virtual computing resources, and other virtualization and network communications overheads. To address these issues, we have designed and implemented C-Meter, which is a portable, extensible, and easy-to-use framework for generating and submitting test workloads to computing clouds. In this paper, first we state the requirements for frameworks to assess the performance of computing clouds. Then, we present the architecture of the C-Meter framework and discuss several cloud resource management alternatives. Finally, we present our early experiences with C-Meter in Amazon EC2. We show how C-Meter can be used for assessing the overhead of acquiring and releasing the virtual computing resources, for comparing different configurations, and for evaluating different scheduling algorithms.

Large-scale distributed computing systems such as grids are serving a growing number of scientists. These environments bring about not only the advantages of an economy of scale, but also the challenges of resource and workload heterogeneity. A consequence of these two forms of heterogeneity is that job runtimes and queue wait times are highly variable, which generally reduces system performance and makes grids difficult to use by the common scientist. Predicting job runtimes and queue wait times have been widely studied for parallel environments. However, there is no detailed investigation on how the proposed prediction methods perform in grids, whose resource structure and workload characteristics are very different from those in parallel systems. In this paper, we assess the performance and benefit of predicting job runtimes and queue wait times in grids based on traces gathered from various research and production grid environments. First, we evaluate the performance of simple yet widely used time series prediction methods and the effect of applying them to different types of job classes (e.g., all jobs submitted by single users or to single sites). Then, we investigate the performance of two kinds of queue wait time prediction methods for grids. Last, we investigate whether prediction-based grid-level scheduling policies can have better performance than policies that do not use predictions.

A well-known problem in P2P systems is freeriding, where users do not share content if there is no incentive to do so. In this paper, we distinguish lazy freeriders that are merely reluctant to share but follow the protocol, versus die-hard freeriders that employ sophisticated methods to subvert the protocol. Existing incentive designs often provide theoretically attractive resistance against die-hard freeriding, yet are rarely deployed in real networks because of practical infeasibility. Meanwhile, real communities benefit greatly from prevention of lazy freeriding, but have only centralized technology available to do so. We present a lightweight, fully distributed mechanism called BARTERCAST that prevents lazy freeriding and is deployed in practice. BarterCast uses a maxflow reputation algorithm based on a peer's private history of its data exchanges as well as indirect information received from other peers. We assess different reputation policies under realistic, trace-based community conditions and show that our mechanism is consistent and effective, even when significant fractions of peers spread false information. Furthermore, we present results of the deployment of BarterCast in the BitTorrent-based Tribler network which currently has thousands of users worldwide.

The BitTorrent protocol is by far the most popular protocol for offline peer-to-peer video distribution on the Internet. BitTorrent has previously been extended to support the streaming of recorded video, that is, Video-on-Demand (VoD). In this paper, we take this support for video streaming a step further by presenting extensions to BitTorrent for supporting live video streaming, which we have implemented in our BitTorrent client called Tribler. We have tested our extensions both by running simulations, and by deploying our implementation in a public trial in the Internet, using the optimal values of several parameters as found in the simulations. We analyse the performance of Tribler in systems with varying values for the percentage of peers behind a firewall or NAT, which we consider to be one of the key parameters in the performance of deployed P2P systems. Our public trial lasted 9 days, during which 4555 unique peers participated from around the globe. We found 61% of the peers to be behind a firewall, a level at which our simulations still indicate acceptable performance. Most of the peers indeed obtained good performance, with for instance a very low prebuffering time before playback starts, indicating the feasibility of our approach. The median prebuffering time we measured was 3.6 seconds, which is 3-10 times shorter than the prebuffering time measured in other deployed peer-to-peer systems.

A number of analytical models exists that capture various properties of the BitTorrent protocol. However, until now virtually all of these models have been based on the assumption that the peers in the system have homogeneous bandwidths. As this is highly unrealistic in real swarms, these models have very limited applicability. Most of all, these models implicitly ignore BitTorrent's most important property: peer selection based on the highest rate of reciprocity. As a result, these models are not suitable for understanding or predicting the properties of real BitTorrent networks. Furthermore, they are hardly of use in the design of realistic BitTorrent simulators and new P2P protocols. In this paper, we extend existing work by presenting a model of a swarm in BitTorrent where peers have arbitrary upload and download bandwidths. In our model we group peers with (roughly) the same bandwidth in classes, and then analyze the allocation of upload slots from peers in one class to peers in another class. We show that our model accurately predicts the bandwidth clustering phenomenon observed experimentally in other work, and we analyze the resulting data distribution in swarms. We validate our model with experiments using real BitTorrent clients. Our model captures the effects of BitTorrent's well-known `tit-for-tat' mechanism in bandwidth-inhomogeneous swarms and provides an accurate mathematical description of the resulting dynamics.

Ever more scientists are employing large-scale distributed systems such as grids for their computational work, instead of tightly coupled high-performance computing systems. However, while these distributed systems are more cost-effective, their heterogeneity in terms of hardware, software, and systems administration, and the lack of accurate resource information leads to inefficient scheduling. In addition, and in contrast to the workloads of tightly coupled high-performance computing systems, a large part of the workloads submitted to these distributed systems consists of large sets (bags) of sequential tasks. Therefore, a realistic performance analysis of scheduling bags-of-tasks in large-scale distributed systems is important. Towards this end, we introduce in this paper a realistic workload model for bags-of-tasks, and we explore through trace-based simulations the design space of scheduling bags-of-tasks. Finally, we identify three new scheduling policies that use only inaccurate information when scheduling, and we compare them against known classes of proposed scheduling policies.

The popular and well-known BitTorrent peer-to-peer protocol offers fast file distribution in a highly scalable way. Several studies have investigated the properties of this protocol, mostly focusing on heterogeneous end-user environments such as the Internet, with asymmetric connections. In this paper however, we focus on the usage of the BitTorrent protocol in homogeneous local environments with symmetric bandwidth properties. Compared with a traditional client-server setup, the use of BitTorrent in such settings can offer huge benefits in performance and scalability, allowing bandwidth sharing and high speed file distribution. We aim to improve the performance of such networks with a novel mechanism for replication using so-called replicators, which replicate a subset of the files in the system. A mathematical model of the resulting Replicated BitTorrent is presented and validated by emulation. Furthermore, we present simulation results that provide insight in the performance of Replicated BitTorrent networks with dynamic peer arrivals and departures. The results show that Replicated BitTorrent significantly improves download times in local bandwidth-symmetric BitTorrent networks.

Peer-to-peer file-sharing networks depend on peers uploading data to each other. Some peers, called free-riders, will not upload data unless there is an incentive to do so. Algorithms designed to prevent free-riding typically assume that connectivity is not a problem. However, on the Internet, a large fraction of the peers resides behind a firewall or NAT, making them unable to accept incoming connections. In this paper, we will prove that it is impossible to prevent free-riding when more than half of the peers are firewalled, and we will provide bounds on the sharing ratios (defined as the number of bytes uploaded divided by the number of bytes downloaded) of both firewalled and non-firewalled peers. Firewall puncturing techniques are complex but can be used to connect two firewalled peers; we will provide a bound on their required effectiveness in order to achieve fairness.We confirm our theory by simulating individual BitTorrent swarms (sets of peers that download the same file), and show that the theoretical bounds can be met in systems with many firewalled peers. We have also collected statistics covering thousands of BitTorrent swarms in several communities, both open and closed; the latter ban peers if their sharing ratios drop below a certain treshhold. We found 45% of the peers to be firewalled in the closed communities, as opposed to 66% in the open communities, which correlates with our theory that to obtain fair sharing ratios for all peers, at most half of them can be behind firewalls.

Today's massively multiplayer online games (MMOGs) can include millions of concurrent players spread across the world. To keep these highly-interactive virtual environments online, a MMOG operator may need to provision tens of thousands of computing resources from various data centers. Faced with large resource demand variability, and with misfit resource renting policies, the current industry practice is to maintain for each game tens of self-owned data centers. In this work we investigate the dynamic resource provisioning from external data centers for MMOG operation. We introduce a novel MMOG workload model that represents the dynamics of both the player population and the player interactions. We evaluate several algorithms, including a novel neural network predictor, for predicting the resource demand. Using trace-based simulation, we evaluate the impact of the data center policies on the resource provisioning efficiency; we show that dynamic provisioning can be much more efficient than its static alternative.

Abstract In multicluster systems, and more generally in grids, jobs may require co‐allocation, that is, the simultaneous or coordinated access of single applications to resources of possibly multiple types in multiple locations managed by different resource managers. Co‐allocation presents new challenges to resource management in grids, such as locating sufficient resources in geographically distributed sites, allocating and managing resources in multiple, possibly heterogeneous sites for single applications, and coordinating the execution of single jobs at multiple sites. Moreover, as single jobs now may have to rely on multiple resource managers, co‐allocation introduces reliability problems. In this paper, we present the design and implementation of a co‐allocating grid scheduler named KOALA that meets these co‐allocation challenges. In addition, we report on the results of an analysis of the performance in our multicluster testbed of the co‐allocation policies built into KOALA. We also include the results of a performance and reliability test of KOALA while our testbed was unstable. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract Most current peer‐to‐peer (P2P) file‐sharing systems treat their users as anonymous, unrelated entities, and completely disregard any social relationships between them. However, social phenomena such as friendship and the existence of communities of users with similar tastes or interests may well be exploited in such systems in order to increase their usability and performance. In this paper we present a novel social‐based P2P file‐sharing paradigm that exploits social phenomena by maintaining social networks and using these in content discovery, content recommendation, and downloading. Based on this paradigm's main concepts such as taste buddies and friends, we have designed and implemented the TRIBLER P2P file‐sharing system as a set of extensions to BitTorrent. We present and discuss the design of TRIBLER, and we show evidence that TRIBLER enables fast content discovery and recommendation at a low additional overhead, and a significant improvement in download performance. Copyright © 2007 John Wiley & Sons, Ltd.

The Grid promise is starting to materialize today: large- scale multi-site infrastructures have grown to assist the work of scientists from all around the world. This tremendous growth can be sustained and continued only through a higher quality of the middleware, in terms of deployability and of correct functionality. A potential solution to this problem is the adoption of industry practices regarding middleware building and testing. However, it is unclear what good build-and-test environments for grid middleware should look like, and how to use them efficiently. In this work we address both these problems. First, we study the characteristics of the NMI build-and-test environment, which handles millions of testing tasks annually, for major Grid middleware such as Condor, Globus, VDT, and gLite. Through the analysis of a system-wide trace covering the past two years we find the main characteristics of the workload, as well as the performance of the system under load. Second, we propose mechanisms for more efficient test management and operation, and for resource provisioning and evaluation. Notably, we propose a generic test optimization technique that reduces the test time by 95%, while achieving 93% of the maximum accuracy, under real conditions.

In large-scale distributed execution environments such as multicluster systems and grids, resource availability may vary due to resource failures and because resources may be added to or withdrawn from such environments at any time. In addition, single sites in such systems may have to deal with workloads originating from both local users and from many other sources. As a result, application malleability, that is, the property of applications to deal with a varying amount of resources during their execution, may be very beneficial for performance. In this paper we present the design of the support of and scheduling policies for malleability in our Koala multicluster scheduler with the help of our Dynaco framework for application malleability. In addition, we show the results of experiments with scheduling malleable workloads with Koala in our DAS multicluster testbed.

Super-peer architectures exploit the heterogeneity of nodes in a P2P network by assigning additional responsi- bilities to higher-capacity nodes. In the design of a super- peer network for file sharing, several issues have to be ad- dressed: how client peers are related to super-peers, how super-peers locate files, how the load is balanced among the super-peers, and how the system deals with node failures. In this paper we introduce a self-organizing super-peer net- work architecture (SOSPNET) that solves these issues in a fully decentralized manner. SOSPNET maintains a super- peer network topology that reflects the semantic similarity of peers sharing content interests. Super-peers maintain se- mantic caches of pointers to files which are requested by peers with similar interests. Client peers, on the other hand, dynamically select super-peers offering the best search per- formance. We show how this simple approach can be em- ployed not only to optimize searching, but also to solve gen- erally difficult problems encountered in P2P architectures such as load balancing and fault tolerance. We evaluate SOSPNET using a model of the semantic structure derived from the 8-month traces of two large file-sharing communi- ties. The obtained results indicate that SOSPNET achieves close-to-optimal file search performance, quickly adjusts to changes in the environment (node joins and leaves), sur- vives even catastrophic node failures, and efficiently dis- tributes the system load taking into account peer capacities.

The grid vision of a single computing utility has yet to materíalize: while many grids with thousands of processors each exist, most work in isolation. An important obstacle for the effective and efficient inter-operation of grids is the problem of resource selection. In this paper we propose a solution to this problem that combines the hierarchical and decentralized approaches for interconnecting grids. In our solution, a hierarchy of grid sites is augmented with peer-to-peer connections between sites under the same administrative control. To operate this architecture, we employ the key concept of delegated matchmaking, which temporarily binds resources from remote sites to the local environment. With trace-based simulations we evaluate our solution under various infrastructural and load conditions, and we show that it outperforms other approaches to inter-operating grids. Specifically, we show that delegated matchmaking achieves up to 60% more goodput and completes 26% more jobs than its best alternative.

The main purpose of many current peer-to-peer (P2P) networks is off-line file sharing. However, a potentially very promising use of such networks is to share video streams (e.g., TV programs) in real time. In order to do so, the peers in a P2P network who are interested in the same video stream may employ Application Level Multicasting (ALM). In existing P2P networks, peers may exhibit behavior which is problematic for ALM: they are not always willing to donate resources (free-riding), and they may arrive and depart at a high rate (churn). In this paper we propose the Orchard algorithm for creating and maintaining ALM trees in P2P networks, which deals with both these problems. By employing a technique called Multiple Description Coding, we split a video stream into several substreams. Orchard creates a dynamic spanning tree for each of these substreams in such a way that in the resulting forest, no peer has to forward more substreams than it receives. Based on an analysis of the expected performance of Orchard and on experiments in a real system, we find that Orchard is capable of maintaining a multicast forest, even when peers join and leave the forest at a high rate.

Building multicluster systems out of multiple, geographically distributed clusters interconnected by high-speed wide-area networks can provide access to a larger computational power and to a wider range of resources. Jobs running on multiclusters and, more generally, in grids, may require (processor) coallocation, i.e., the simultaneous allocation of resources (processors) in different clusters or subsystems of a grid. In this paper, we propose four scheduling policies for processor coallocation in multiclusters, and we assess with simulations their performance under a wide variety of parameter settings. In particular, in our simulations we use synthetic workloads and workloads derived from the logs of actual systems and from runtime measurements. We conclude that although coallocation makes scheduling more difficult and the wide-area communication critically impacts the performance, there is a wide range of realistic applications that may benefit from coallocation. However, unrestricted coallocation is not recommended: Limiting the total job size or the number or the sizes of their components improves performance.

Grid computing is becoming the natural way to aggregate and share large sets of heterogeneous resources. With the infrastructure becoming ready for the challenge, current grid development and acceptance hinge on proving that grids reliably support real applications, and on creating adequate benchmarks to quantify this support. However, grid applications are just beginning to emerge, and traditional benchmarks have yet to prove representative in grid environments. To address this chicken-and-egg problem, we propose a middle-way approach: create and run synthetic grid workloads comprising applications representative for today’s grids. For this purpose, we have designed and implemented GRENCHMARK, a framework for synthetic workload generation and submission. The framework greatly facilitates synthetic workload modeling, comes with over 35 synthetic and real applications, and is extensible and flexible. We show how the framework can be used for grid system analysis, functionality testing in grid environments, and for comparing different grid settings, and present the results obtained with GRENCHMARK in our multi-cluster grid, the DAS

Grid applications are increasingly being developed as workflows built of well-structured, reusable components. We develop a user-transparent scheduling approach for Higher-Order Components (HOCs) . parallel implementations of typical programming patterns, accessible and customizable via Web services. We introduce a set of cost functions for a reusable scheduling: when the workflow recurs, it is mapped to the same execution nodes, avoiding the need for a repeated scheduling phase. We prove the efficiency of our scheduling by implementing it within the KOALA scheduler and comparing it with KOALA's standard Closeto- File policy. Experiments on scheduling HOC-based applications achieve a 40% speedup in communication and a 100% throughput increase.

Grid computing is becoming the natural way to aggregate and share large and heterogeneous sets of resources. However, grid development and acceptance hinge on proving that grids reliably support large communities of users, and their real applications. In this paper we assess the ability of existing grid infrastructures to provision resources for a class of applications with numerous potential users, namely the class of world-wide data-sharing services. For this purpose, we first analyze the requirements of this class of applications, and match them against the existing spare capacity in three existing large-scale grid environments, namely OSG/Grid3, NorduGrid, and CERN LCG. Having shown that the existing capacity is insufficient, we devise and assess through trace-based simulation five domainspecific scheduling policies. Our findings give evidence that grid technology could be successfully leveraged for worldwide data-sharing services, without impacting the level of service for the currently existing load.

In multicluster systems, and more generally, in grids, parallel applications may require co-allocation, i.e., the simultaneous allocation of resources such as processors in multiple clusters. Although co-allocation enables the allocation of more processors than available on a single cluster, depending on the applications' communication characteristics, it has the potential disadvantage of increased execution times due to relatively slow wide-area communication. In this paper, we present two job placement policies, the Cluster Minimization and the Flexible Cluster Minimization policies which take into account the wide-area communication overhead when co-allocating applications across the clusters. We have implemented these policies in our grid scheduler called KOALA in order to serve different job request types. To assess the performance of the policies, we perform experiments in a real multicluster testbed using communication-intensive parallel applications.

P2P systems that rely on the voluntary contribution of bandwidth by the individual peers may suffer from free riding. To address this problem, mechanisms enforcing fairness in bandwidth sharing have been designed, usually by limiting the download bandwidth to the available upload bandwidth. As in real environments the latter is much smaller than the former, these mechanisms severely affect the download performance of most peers. In this paper we propose a system called 2Fast, which solves this problem while preserving the fairness of bandwidth sharing. In 2Fast, we form groups of peers that collaborate in downloading a file on behalf of a single group member, which can thus use its full download bandwidth. A peer in our system can use its currently idle bandwidth to help other peers in their ongoing downloads, and get in return help during its own downloads. We assess the performance of 2Fast analytically and experimentally, the latter in both real and simulated environments. We find that in realistic bandwidth limit settings, 2Fast improves the download speed by up to a factor of 3.5 in comparison to state-of-the-art P2P download protocols

The main purpose of many current peer-to-peer (P2P) networks is off-line file sharing. However, a potentially very promising use of such networks is to share video streams (e.g., TV programs) in real time. In order to do so, the peers in a P2P network who are interested in the same video stream may employ application level multicasting (ALM). In existing P2P networks, peers may exhibit behaviour which is problematic for ALM: peers tend not to donate any resources (free-riding), and they arrive and depart at a high rate (churn). In this paper we propose the orchard algorithm for ALM of video streams in P2P systems, which deal with both these problems. By employing a technique called multiple description coding, we split a video stream into several substreams. Orchard creates a dynamic spanning tree for each of these substreams in such a way that in the re suiting forest, no peer has to forward more substreams than it receives. Our experiments show that orchard is capable of providing a good quality of service to every peer, even when peers join and leave the forest at a high rate

In multicluster systems, and more generally, in grids, jobs may require co-allocation, i.e., the simultaneous allocation of resources such as processors and input files in multiple clusters. While such jobs may have reduced runtimes because they have access to more resources, waiting for processors in multiple clusters and for the input files to become available in the right locations, may introduce inefficiencies. Moreover, as single jobs now have to rely on multiple resource managers, co-allocation introduces reliability problems. In this paper, we present two additions to the original design of our KOALA co-allocating scheduler (different priority levels of jobs and incrementally claiming processors), and we report on our experiences with KOALA in our multicluster testbed while it was unstable.

In multicluster systems, and more generally, in grids, jobs may require coallocation, i.e., the simultaneous allocation of resources such as processors and input files in multiple clusters. While such jobs may have reduced runtimes because they have access to more resources, waiting for processors in multiple clusters and for the input files to become available in the right locations may introduce inefficiencies. In previous work, we have studied through simulations only processor coallocation. Here, we extend this work with an analysis of the performance in a real testbed of our prototype processor and data coallocator with the close-to-files (CF) job-placement algorithm. CF tries to place job components on clusters with enough idle processors which are close to the sites where the input files reside. We present a comparison of the performance of CF and the worst-fit job-placement algorithm, with and without file replication, achieved with our prototype. Our most important findings are that CF with replication works best, and that the utilization in our testbed can be driven to about 80%.

Peer-to-peer (P2P) networks are generally considered to be free havens for pirated content, in particular with respect to music. We describe a solution for the problem of copyright infringement in P2P networks for music sharing. In particular, we propose a P2P protocol that integrates the functions of identification, tracking, and sharing of music with those of licensing, monitoring, and payment. This highly decentralized music-aware P2P protocol will allow access to large amounts of music of guaranteed quality; it merges in a natural way the policing functions for copyright protection and an efficient music-management infrastructure for the benefit of the user.

In systems consisting of multiple clusters of processors which are interconnected by relatively slow communication links and which employ space sharing for scheduling jobs, such as our Distributed ASCI Supercomputer (DAS), co-allocation, i.e., the simultaneous allocation of processors to single jobs in different clusters, may be required. We study the performance of co-allocation by means of simulations for the mean response time of jobs depending on the structure and sizes of jobs, the scheduling policy, and the communication speed ratio. Our main conclusion is that for current communication speed ratios in multiclusters, coallocation is a viable option.

In systems consisting of multiple clusters of processors which employ space sharing for scheduling jobs, such as our Distributed ASCI (Advanced School for Computing Imaging) Supercomputer (DAS), co-allocation, i.e., the simultaneous allocation of processors to single jobs in multiple clusters, may be required. In this paper we study the performance of several scheduling policies for co-allocating unordered requests in multiclusters with a workload derived from the DAS. We find that beside the policy, limiting the total job size significantly improves the performance, and that for a slowdown of jobs due to global communication bounded by 1.25, co-allocation is a viable choice.

In systems consisting of multiple clusters of processors interconnected by relatively slow communication links, co-allocation may be required. We study its performance by means of simulations, depending on the structure and sizes of jobs, and the communication speed ratio. We model a multicluster with C clusters of identical processors. The workload consists of rigid jobs that require fixed numbers of processors, possibly in multiple clusters simultaneously. A job is represented by a tuple of C values, each generated from a same distribution D. In an ordered request the positions of the components in the tuple specify the clusters from which the processors must be allocated. For an unordered request, by the components of the tuple the job only specifies the numbers of processors needed in the separate clusters. A flexible request specifies the total number of processors, obtained as the sum of the values in the tuple. For total requests, there is a single cluster and a request only specifies the total number of processors needed. All intracluster communication links have the same speed, as do all intercluster links. The communication speed ratio is the ratio between the time needed to complete a send operation between processors in different clusters and in the same cluster.

In systems consisting of multiple clusters of processors such as our Distributed ASCI Supercomputer (DAS), jobs may request co-allocation, i.e., the simultaneous allocation of processors in different clusters. We simulate such systems ignoring communication among the tasks of jobs, and determine the response times for different types and sizes of job requests, and for different numbers and sizes of clusters. In many cases we also compute or approximate the maximum utilization. We find that the numbers and sizes of the clusters and of the job components have a strong impact on performance, and that in many cases co-allocation is a viable choice.

Decay-usage scheduling is a priority-aging time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires CPU time, and by increasing its priority when it does not use the (a) CPU. In this article we deal with a decay-usage scheduling policy in multiprocessors modeled after widely used systems. The priority of a job consists of a base priority and a time-dependent component based on processor usage. Because t he priorities in our model are time dependent, a queuing-theoretic analysis—for instance, for the mean job response time—seems impossible. Still, it turns out that as a consequence of the scheduling policy, the shares of the available CPU time obtained by jobs converge, and a deterministic analysis for these shares is feasible: We show how for a fixed set of jobs with large processing demands, the steady-state shares can be obtained given the base priorities, and conversely, how to set the base priorities given the required shares. In addition, we analyze the relation between the values of the scheduler parameters and the level of control it can exercise over the steady-state share ratios, and we deal with the rate of convergence. We validate the model by simulations and by measurements of actual systems.

Priority-ageing or decay-usage scheduling is a time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires CPU time, and by increasing its priority when it does not use the (a) CPU. In this paper we deal with a decay-usage scheduling policy in multiprocessor systems modeled after widely used systems. The priority of a job consists of a base priority and a time-dependent part based on processor usage. Because the priorities in our model are time dependent, a queueing-theoretic analysis, for instance for the mean response time, seems impossible. Still, it turns out that as a consequence of the scheduling policy, the shares of available CPU time obtained by jobs converge, and a deterministic analysis for these shares is feasible: for a fixed set of jobs with very large (infinite) processing demands, we derive the relation between their base priorities and their steady-state shares. In addition, we analyze the relation between the values of the parameters of the scheduler and the level of control it can exercise over the steady-state shares. We validate the model by simulations and by measurements of actual systems.