Search

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice.

To run proper Big Data Analytics, small and medium enterprises (SMEs) need to acquire expertise, hardware and software, which often translates to relevant initial investments for activities not directly connected to the company's business. To reduce such investments, the TOREADOR project proposes a Big Data Analytics framework which supports users in devising their own Big Data solutions by keeping the inherent costs at a minimum, and leveraging pre-existent knowledge and expertise. Among the objectives of the TOREADOR framework is supporting developers in parallelizing and deploying their Big Data algorithms, in order to develop their own analytics solutions. This paper describes the Code-Based approach, adopted within the TOREADOR framework to parallelize users’ algorithms and deploy them on distributed platforms, via the annotation of parallelizable code portions with parallelization primitives. The approach, which relies on the guidance of Parallel Patterns to implement the parallelization, and on Skeletons to automatically build execution and deployment templates, is realized through a source-to-source Compiler, also described in the present paper.

Along with the development of cloud computing, more and more applications are migrated into the cloud. An important feature of cloud computing is pay-as-you-go. However, most users always should pay more than their actual usage due to the one-hour billing cycle. In addition, most cloud service providers provide a certain discount for long-term users, but short-term users with small computing demands cannot enjoy this discount. To reduce the cost of cloud users, we introduce a new role, which is cloud broker . A cloud broker is an intermediary agent between cloud providers and cloud users. It rents a number of reserved VMs from cloud providers with a good price and offers them to users on an on-demand basis at a cheaper price than that provided by cloud providers. Besides, the cloud broker adopts a shorter billing cycle compared with cloud providers. By doing this, the cloud broker can reduce a great amount of cost for user. In addition to reduce the user cost, the cloud broker also could earn the difference in prices between on-demand and reserved VMs. In this paper, we focus on how to configure a cloud broker and how to price its VMs such that its profit can be maximized on the premise of saving costs for users. Profit of a cloud broker is affected by many factors such as the user demands, the purchase price and the sales price of VMs, the scale of the cloud broker, etc.. Moreover, these factors are affected mutually, which makes the analysis on profit more complicated. In this paper, we first give a synthetically analysis on all the affecting factors, and define an optimal multiserver configuration and VM pricing problem which is modeled as a profit maximization problem. Second, combining the partial derivative and bisection search method, we propose a heuristic method to solve the optimization problem. The near-optimal solutions can be used to guide the configuration and VM pricing of the cloud broker. Moreover, a series of comparisons are given which show that a cloud broker can save a considerable cost for users.

The paper surveys the state of the art of task scheduling in Desktop Grid computing systems. We describe the general architecture of a Desktop Grid system and the computing model adopted by the BOINC middleware. We summarize research papers to bring together and examine the optimization criteria and methods proposed by researchers so far for improving Desktop Grid task scheduling (assigning tasks to computing nodes by a server). In addition, we review related papers, which address non-regular architectures, like hierarchical and peer-to-peer Desktop Grids, as well as Desktop Grids designed for solving interdependent tasks.

Now we are entering the era of the Internet of Everything (IoE) and billions of sensors and actuators are connected to the network. As one of the most sophisticated IoE applications, real-time video analytics is promising to significantly improve public safety, business intelligence, and healthcare & life science, among others. However, cloud-centric video analytics requires that all video data must be preloaded to a centralized cluster or the cloud, which suffers from high response latency and high cost of data transmission, given the scale of zettabytes of video data generated by IoE devices. Moreover, video data is rarely shared among multiple stakeholders due to various concerns, which restricts the practical deployment of video analytics that takes advantages of many data sources to make smart decisions. Furthermore, there is no efficient programming interface for developers and users to easily program and deploy IoE applications across geographically distributed computation resources. In this paper, we present a new computing framework, Firework , which facilitates distributed data processing and sharing for IoE applications via a virtual shared data view and service composition. We designed an easy-to-use programming interface for Firework to allow developers to program on Firework . This paper describes the system design, implementation, and programming interface of Firework . The experimental results of a video analytics application demonstrate that Firework reduces up to 19.52 percent of response latency and at least 72.77 percent of network bandwidth cost, compared to a cloud-centric solution.

In real simulation applications, simulations often involve large volumes of three-dimensinal (3D) moving objects. With the rapid growth of the scale of simulation-problem domains, it has become a key requirement to efficiently manage massive 3D moving objects. Conventional indexing approaches for managing 3D moving objects during simulations generally suffer from excessive update costs. Aiming to this problem, this paper first proposes an update-efficient indexing structure by fusing a loose Octree and one update-memo structure, namely ML-Octree. ML-Octree significantly reduces the update costs of one simulation involving massive 3D moving objects. Towards providing a more efficient indexing approach, this paper has explored the feasibility of paralleling ML-Octree by employing Graphic Processing Unit (GPU). A load-balancing scheme is used to further improve the update performance of the GPU-aided ML-Octree. Finally, a distributed GPU-aided ML-Octree is proposed for large-scale simulations. The experimental results indicate that (1) ML-Octree can acquire the update-performance gain of an order of magnitude similar to that of Octree, (2) the GPU-aided ML-Octree can accelerate 5.07 $\times$ faster than a parallel ML-Octree with 8 CPU threads on average, (3) the load-balance scheme can improve GPU-aided ML-Octree by 2.3 $\times$ on average, and (4) the distributed GPU-aided ML-Octree can efficiently support large-scale simulations.

This paper presents a detailed analysis of the application of Hardware Transactional Memory (HTM) support for loop parallelization with Thread-Level Speculation (TLS) and describes a careful evaluation of the implementation of TLS on the HTM extensions available in such machines. The sample implementation of TLS over HTM described in this paper also provides evidence that the programming effort to implement TLS over HTM support is non-trivial. Thus the paper also describes an extension to OpenMP that both makes TLS more accessible to OpenMP programmers and allows for the easy tuning of TLS parameters. As a result, it provides evidence to support several important claims about the performance of TLS over HTM in the Intel Core and the IBM POWER8 architectures. Experimental results reveal that by implementing TLS on top of HTM, speed-ups of up to 3.8 $\times$ can be obtained for some loops.

In this paper, we present GDA, a generalized decision aggregation framework that integrates information from distributed sensor nodes for decision making in a resource efficient manner. Different from traditional approaches, our proposed GDA framework is able to not only estimate the reliability of each sensor, but also take advantage of its confidence information, and thus achieves higher decision accuracy. Targeting generalized problem domains, our framework can naturally handle the scenarios where different sensor nodes observe different sets of events whose numbers of possible classes may also be different. GDA also makes no assumption about the availability level of ground truth label information, while being able to take advantage of any if present. For these reasons, our approach can be applied to a much broader spectrum of sensing scenarios. In this paper, we also propose two extensions of the GDA framework, i.e., incremental GDA (I-GDA) and parallel GDA (P-GDA) to deal with streaming and large-scale data. The advantages of our proposed methods are demonstrated through both theoretic analysis and extensive experiments.

Deep Neural Networks (DNNs) have recently been shown to significantly outperform existing machine learning techniques in several pattern recognition tasks. DNNs are the state-of-the-art models used in image recognition, object detection, classification and tracking, and speech and language processing applications. The biggest drawback to DNNs has been the enormous cost in computation and time taken to train the parameters of the networks - often a tenfold increase relative to conventional technologies. Such training time costs can be mitigated by the application of parallel computing algorithms and architectures. However, these algorithms often run into difficulties because of the cost of inter-processor communication bottlenecks. In this paper, we describe how to enable Parallel Deep Neural Network Training on the IBM Blue Gene/Q (BG/Q) computer system. Specifically, we explore DNN training using the data parallel Hessian-free 2nd order optimization algorithm. Such an algorithm is particularly well-suited to parallelization across a large set of loosely coupled processors. BG/Q, with its excellent inter-processor communication characteristics, is an ideal match for this type of algorithm. The paper discusses how issues regarding programming model and data-dependent imbalances are addressed. Results on large-scale speech tasks show that the performance on BG/Q scales linearly up to 4096 processes with no loss in accuracy. This allows us to train neural networks using billions of training examples in a few hours.

Hundreds of papers on job scheduling for distributed systems are published every year and it becomes increasingly difficult to classify them. Our analysis revealed that half of these papers are barely cited. This paper presents a general taxonomy for scheduling problems and solutions in distributed systems. This taxonomy was used to classify and make publicly available the classification of $109$ scheduling problems and their solutions. These $109$ problems were further clustered into ten groups based on the features of the taxonomy. The proposed taxonomy will facilitate researchers to build on prior art, increase new research visibility, and minimize redundant effort.

MapReduce, originally developed by Google for search applications, has recently become a popular programming framework for parallel and distributed environments. This paper presents an energy-efficient architecture design for MapReduce on Field Programmable Gate Arrays (FPGAs). The major goal is to enable users to program FPGAs with simple MapReduce interfaces, and meanwhile to embrace automatic performance optimizations within the MapReduce framework. Compared to other processors like CPUs and GPUs, FPGAs are (re-)programmable hardware and have very low energy consumption. However, the design and implementation of MapReduce on FPGAs can be challenging: firstly, FPGAs are usually programmed with hardware description languages, which hurts the programmability of the MapReduce design to its users; secondly, since MapReduce has irregular access patterns (especially in the reduce phase) and needs to support user-defined functions, careful designs and optimizations are required for efficiency. In this paper, we design, implement and evaluate Melia , a MapReduce framework on FPGAs. Melia takes advantage of the recent OpenCL programming framework developed for Altera FPGAs, and abstracts FPGAs behind the simple and familiar MapReduce interfaces in C. We further develop a series of FPGA-centric optimization techniques to improve the efficiency of Melia, and a cost- and resource-based approach to automate the parameter settings for those optimizations. We evaluate Melia on a recent Altera Stratix V GX FPGA with a number of commonly used MapReduce benchmarks. Our results demonstrate that 1) the efficiency and effectiveness of our optimizations and automated parameter setting approach, 2) Melia can achieve promising energy efficiency in comparison with its counterparts on CPUs/GPUs on both single-FPGA and cluster settings.

As systems scale toward exascale, many resources will become increasingly constrained. While some of these resources have historically been explicitly allocated, many—such as network bandwidth, I/O bandwidth, or power—have not. As systems continue to evolve, we expect many such resources to become explicitly managed. This change will pose critical challenges to resource management and job scheduling. In this paper, we explore the potential of relaxing network allocation constraints for Blue Gene systems. Our objective is to improve the batch scheduling performance, where the partition-based interconnect architecture provides a unique opportunity to explicitly allocate network resources to jobs. This paper makes three major contributions. The first is substantial benchmarking of parallel applications, focusing on assessing application sensitivity to communication bandwidth at large scale. The second is three new scheduling schemes using relaxed network allocation and targeted at balancing individual job performance with overall system performance. The third is a comparative study of our scheduling schemes versus the existing scheduler on Mira, a 48-rack Blue Gene/Q system at Argonne National Laboratory. Specifically, we use job traces collected from this production system.

Proliferation of virtualized systems opens a new opportunity to improve the scalability of multi-core architectures. Among the scalability bottlenecks in multi-cores, cache coherence has been one of the most critical problems. Although snoop-based protocols have been dominating commercial multi-core designs, it has been difficult to scale them for more cores, as snooping protocols require high network bandwidth and power consumption for snooping all the caches.In this paper, we propose a novel snoop-based cache coherence protocol, called virtual snooping, for virtualized multi-core architectures. Virtual snooping exploits memory isolation across virtual machines and prevents unnecessary snoop requests from crossing the virtual machine boundaries. Each virtual machine becomes a virtual snoop domain, consisting of a subset of the cores in a system. Although the majority of virtual machine memory is isolated, sharing of cachelines across VMs still occur. To address such data sharing, this paper investigates three factors, data sharing through the hypervisor, virtual machine relocation, and content-based sharing. In this paper, we explore the design space of virtual snooping with experiments on emulated and real virtualized systems including the mechanisms and overheads of the hypervisor. In addition, the paper discusses the scheduling impact on the effectiveness of virtual snooping.

Recent trends of increasing core-count and memory/bandwidth-wall have led to major overhauls in chip architecture. In face of increasing cache capacity demands, researchers have now explored DRAM, which was conventionally considered synonymous to main memory, for designing large last level caches. Efficient integration of DRAM caches in mainstream computing systems, however, also presents several challenges and several recent techniques have been proposed to address them. In this paper, we present a survey of techniques for architecting DRAM caches. Also, by classifying these techniques across several dimensions, we underscore their similarities and differences. We believe that this paper will be very helpful to researchers for gaining insights into the potential, tradeoffs and challenges of DRAM caches.

Object detection is a fundamental challenge facing intelligent applications. Image processing is a promising approach to this end, but its computational cost is often a significant problem. This paper presents schemes for accelerating the deformable part models (DPM) on graphics processing units (GPUs). DPM is a well-known algorithm for image-based object detection, and it achieves high detection rates at the expense of computational cost. GPUs are massively parallel compute devices designed to accelerate data-parallel compute-intensive workload. According to an analysis of execution times, approximately 98 percent of DPM code exhibits loop processing, which means that DPM could be highly parallelized by GPUs. In this paper, we implement DPM on the GPU by exploiting multiple parallelization schemes. Results of an experimental evaluation of this GPU-accelerated DPM implementation demonstrate that the best scheme of GPU implementations using an NVIDIA GPU achieves a speed up of 8.6x over a naive CPU-based implementation.

Cloud data owners prefer to outsource documents in an encrypted form for the purpose of privacy preserving. Therefore it is essential to develop efficient and reliable ciphertext search techniques. One challenge is that the relationship between documents will be normally concealed in the process of encryption, which will lead to significant search accuracy performance degradation. Also the volume of data in data centers has experienced a dramatic growth. This will make it even more challenging to design ciphertext search schemes that can provide efficient and reliable online information retrieval on large volume of encrypted data. In this paper, a hierarchical clustering method is proposed to support more search semantics and also to meet the demand for fast ciphertext search within a big data environment. The proposed hierarchical approach clusters the documents based on the minimum relevance threshold, and then partitions the resulting clusters into sub-clusters until the constraint on the maximum size of cluster is reached. In the search phase, this approach can reach a linear computational complexity against an exponential size increase of document collection. In order to verify the authenticity of search results, a structure called minimum hash sub-tree is designed in this paper. Experiments have been conducted using the collection set built from the IEEE Xplore. The results show that with a sharp increase of documents in the dataset the search time of the proposed method increases linearly whereas the search time of the traditional method increases exponentially. Furthermore, the proposed method has an advantage over the traditional method in the rank privacy and relevance of retrieved documents.

The processing of massive numbers of small files is a challenge in the design of distributed file systems. Currently, the combined-block-storage approach is prevalent. However, the approach employs the traditional file systems such as ExtFS and may cause inefficiency when accessing small files randomly located in the disk. This paper focuses on optimizing the performance of data servers in accessing massive numbers of small files. We present a Flat Lightweight File System (iFlatLFS) to manage small files, which is based on a simple metadata scheme and a flat storage architecture. iFlatLFS is designed to substitute the traditional file system on data servers and can be deployed underneath distributed file systems that store massive numbers of small files. iFlatLFS can greatly simplify the original data access procedure. The new metadata proposed in this paper occupies only a fraction of the metadata size based on traditional file systems. We have implemented iFlatLFS in CentOS 5.5 and integrated it into an open source Distributed File System (DFS), called Taobao FileSystem (TFS), which is developed by a top B2C service provider, Alibaba, in China and is managing over 28.6 billion small photos. We have conducted extensive experiments to verify the performance of iFlatLFS. The results show that when the file size ranges from 1 to 64 KB, iFlatLFS is faster than Ext4 by 48 and 54 percent on average for random read and write in the DFS environment, respectively. Moreover, after iFlatLFS is integrated into TFS, iFlatLFS-based TFS is faster than the existing Ext4-based TFS by 45 and 49 percent on average for random read access and hybrid access (the mix of read and write accesses), respectively.

Efficient subscription summarization and event matching is key to the scalability of content-based publish/subscribe networks (CPSNs). Current summarization and event matching mechanisms based on subscription subsumption induce heavy event processing load on brokers degrading the performance of CPSNs especially under high rates of churn, i.e., addition, deletion, or modification of subscriptions. Yet, many modern CPS applications such as location-based services or algorithmic trading inherently rely on high frequency subscription changes. This paper describes Beretta, a dynamic CPSN which sustains high throughput and low event-propagation latencies even under a high frequency of subscription changes. Beretta leverages strong event typing and represents all subscriptions in a normalized form as combinations of value intervals and set inclusions without compromising on expressiveness. Beretta’s “split and subsume” broker algorithm reduces the complexity of matching an event from $O(K\,N)$ to $O(K\,\log \,N + |result|)$ , with $N$ being the number of subscriptions for the event type and $K$ the number of its attributes. Event types and normalization are exploited to split subscriptions into predicates on individual event types and attributes and to efficiently regroup these in segment trees and hash maps which yield excellent subsumption properties and support attribute-wise split filtering during event matching. Normalization enables the systematic introduction of parameters into subscriptions to support both parametric and structural updates. This paper also empirically demonstrates the performance improvements due to our techniques through realistic algorithmic trading and highway traffic monitoring benchmarks.

In Distributed Virtual Environments (DVEs), the primary task is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. In thezone-based Multi-server Distributed Virtual Environment (MSDVE), zone mapping and client assignment are two key issues in the design of an efficient and scalable MSDVE. Most of the existing work on the zone mapping and client assignment issues in MSDVE aims to either balance workload among servers, reduce inter-server communication, and/or reduce transmission delay. In this paper, we study the zone mapping and client assignment issues from a new perspective aiming to reduce the inconsistency of a DVE. Using the time-space inconsistency metric, we formally formulate the problem as a mix integer programming problem. The zone mapping and client assignment strategy is proposed which consists of a centralized algorithm for initialization and a distributed adaptive tuningalgorithm for running system. Extensive experiments were conducted both by simulation and real system for evaluating theperformance of the proposed solutions and results are reported in the paper.

This paper aims to design an efficient data forwarding scheme based on local activity and social similarity (LASS) for mobile social networks (MSNs). Various definitions of social similarity have been proposed as the criterion for relay selection, which results in various forwarding schemes. The appropriateness and practicality of various definitions determine the performances of these forwarding schemes. A popular definition has recently been proven to be more efficient than other existing ones, i.e., the more common interests between two nodes, the larger social similarity between them. In this work, we show that schemes based on such definition ignore the fact that members within the same community, i.e., with the same interest, usually have different levels of local activity, which will result in a low efficiency of data delivery. To address this, in this paper, we design a new data forwarding scheme for MSNs based on community detection in dynamic weighted networks, called Local-Activity and Social-Similarity, taking into account the difference of members’ internal activity within each community, i.e., local activity . To the best of our knowledge, the proposed scheme is the first one that utilizes different levels of local activity within communities. Through extensive simulations, we demonstrate that LASS achieves better performance than state-of-the-art protocols.

Restraining the spread of rumors in online social networks (OSNs) has long been an important but difficult problem to be addressed. Currently, there are mainly two types of methods 1) blocking rumors at the most influential users or community bridges, or 2) spreading truths to clarify the rumors. Each method claims the better performance among all the others according to their own considerations and environments. However, there must be one standing out of the rest. In this paper, we focus on this part of work. The difficulty is that there does not exist a universal standard to evaluate them. In order to address this problem, we carry out a series of empirical and theoretical analysis on the basis of the introduced mathematical model. Based on this mathematical platform, each method will be evaluated by using real OSN data. We have done three types of analysis in this work. First, we compare all the measures of locating important users. The results suggest that the degree and betweenness measures outperform all the others in the Facebook network. Second, we analyze the method of the truth clarification method, and find that this method has a long-term performance while the degree measure performs well only in the early stage. Third, in order to leverage these two methods, we further explore the strategy of different methods working together and their equivalence. Given a fixed budget in the real world, our analysis provides a potential solution to find out a better strategy by integrating both types of methods together. From both the academic and technical perspective, the work in this paper is an important step towards the most practical and optimal strategies of restraining rumors in OSNs.

Owing to its attractive features such as fast identification and relatively long interrogating range over the classical barcode systems, radio-frequency identification (RFID) technology possesses a promising prospect in many practical applications such as inventory control and supply chain management. However, unknown tags appear in RFID systems when the tagged objects are misplaced or unregistered tagged objects are moved in, which often causes huge economic losses. This paper addresses an important and challenging problem of unknown tag identification in large-scale RFID systems. The existing protocols leverage the Aloha-like schemes to distinguish the unknown tags from known tags at the slot level, which are of low time-efficiency, and thus can hardly satisfy the delay-sensitive applications. To fill in this gap, two filtering-based protocols (at the bit level) are proposed in this paper to address the problem of unknown tag identification efficiently. Theoretical analysis of the protocol parameters is performed to minimize the execution time of the proposed protocols. Extensive simulation experiments are conducted to evaluate the performance of the protocols. The results demonstrate that the proposed protocols significantly outperform the currently most promising protocols.

In this paper, we propose a new type of incentive-driven and privacy-preserving systems for large-scale message dissemination in mobile networks. To distribute incentives which encourage forwarding behaviors, such as monetary rewards, we want to keep track of the forwarder list. In our algorithms, we rely on a Probabilistic one-ownership forwarding algorithm to record the list, so that the exchanged messages can be kept short and privacy preserving. More specifically, only one hop of forwarder information, instead of the complete list, is recorded, and the information is updated probabilistically following two ownership flipping models, namely, One-Flip and Always-Flip models. We also use a Bluetooth Service Discovery Protocol (SDP) toolkit to enable fast, configuration-free message exchange. Throughout the paper, we use coupon as a typical type of message to illustrate the core ideas. We have implemented the coupon dissemination system in Java ME. Our experiments on real-world mobile phones, such as Nokia and Samsung phones, and large-scale simulations show that our system is efficient in peer-to-peer message distribution and capable of massive deployment. We believe our key methodology can serve as a general framework for facilitating information propagation on mobile phones, where incentives and privacy protection are both essential.

Cloud computing as an emerging technology trend is expected to reshape the advances in information technology. In a cost-efficient cloud environment, a user can tolerate a certain degree of delay while retrieving information from the cloud to reduce costs. In this paper, we address two fundamental issues in such an environment: privacy and efficiency. We first review a private keyword-based file retrieval scheme that was originally proposed by Ostrovsky. Their scheme allows a user to retrieve files of interest from an untrusted server without leaking any information. The main drawback is that it will cause a heavy querying overhead incurred on the cloud and thus goes against the original intention of cost efficiency. In this paper, we present three efficient information retrieval for ranked query (EIRQ) schemes to reduce querying overhead incurred on the cloud. In EIRQ, queries are classified into multiple ranks, where a higher ranked query can retrieve a higher percentage of matched files. A user can retrieve files on demand by choosing queries of different ranks. This feature is useful when there are a large number of matched files, but the user only needs a small subset of them. Under different parameter settings, extensive evaluations have been conducted on both analytical models and on a real cloud environment, in order to examine the effectiveness of our schemes.

This paper presents a performance modeling and optimization analysis tool to predict and optimize the performance of sparse matrix-vector multiplication (SpMV) on GPUs. We make the following contributions: 1) We present an integrated analytical and profile-based performance modeling to accurately predict the kernel execution times of CSR, ELL, COO, and HYB SpMV kernels. Our proposed approach is general, and neither limited by GPU programming languages nor restricted to specific GPU architectures. In this paper, we use CUDA-based SpMV kernels and NVIDIA Tesla C2050 for our performance modeling and experiments. According to our experiments, for 77 out of 82 test cases, the performance differences between the predicted and measured execution times are less than 9 percent; for the rest five test cases, the differences are between 9 and 10 percent. For CSR, ELL, COO, and HYB SpMV CUDA kernels, the average differences are 6.3, 4.4, 2.2, and 4.7 percent, respectively. 2) Based on the performance modeling, we design a dynamic-programming based SpMV optimal solution auto-selection algorithm to automatically report an optimal solution (i.e., optimal storage strategy, storage format(s), and execution time) for a target sparse matrix. In our experiments, the average performance improvements of the optimal solutions are 41.1, 49.8, and 37.9 percent, compared to NVIDIA's CSR, COO, and HYB CUDA kernels, respectively.

The provisioning of basic security mechanisms such as authentication and confidentiality is highly challenging in a content-based publish/subscribe system. Authentication of publishers and subscribers is difficult to achieve due to the loose coupling of publishers and subscribers. Likewise, confidentiality of events and subscriptions conflicts with content-based routing. This paper presents a novel approach to provide confidentiality and authentication in a broker-less content-based publish/subscribe system. The authentication of publishers and subscribers as well as confidentiality of events is ensured, by adapting the pairing-based cryptography mechanisms, to the needs of a publish/subscribe system. Furthermore, an algorithm to cluster subscribers according to their subscriptions preserves a weak notion of subscription confidentiality. In addition to our previous work , this paper contributes 1) use of searchable encryption to enable efficient routing of encrypted events, 2) multicredential routing a new event dissemination strategy to strengthen the weak subscription confidentiality, and 3) thorough analysis of different attacks on subscription confidentiality. The overall approach provides fine-grained key management and the cost for encryption, decryption, and routing is in the order of subscribed attributes. Moreover, the evaluations show that providing security is affordable w.r.t. 1) throughput of the proposed cryptographic primitives, and 2) delays incurred during the construction of the publish/subscribe overlay and the event dissemination.

Policy-based management is a very effective method to protect sensitive information. However, the overclaim of privileges is widespread in emerging applications, including mobile applications and social network services, because the applications' users involved in policy administration have little knowledge of policy-based management. The overclaim can be leveraged by malicious applications, then lead to serious privacy leakages and financial loss. To resolve this issue, this paper proposes a novel policy administration mechanism, referred to as collaborative policy administration (CPA for short), to simplify the policy administration. In CPA, a policy administrator can refer to other similar policies to set up their own policies to protect privacy and other sensitive information. This paper formally defines CPA and proposes its enforcement framework. Furthermore, to obtain similar policies more effectively, which is the key step of CPA, a text mining-based similarity measure method is presented. We evaluate CPA with the data of Android applications and demonstrate that the text mining-based similarity measure method is more effective in obtaining similar policies than the previous category-based method.

Password-authenticated key exchange (PAKE) is where a client and a server, who share a password, authenticate each other and meanwhile establish a cryptographic key by exchange of messages. In this setting, all the passwords necessary to authenticate clients are stored in a single server. If the server is compromised, due to, for example, hacking or even insider attack, passwords stored in the server are all disclosed. In this paper, we consider a scenario where two servers cooperate to authenticate a client and if one server is compromised, the attacker still cannot pretend to be the client with the information from the compromised server. Current solutions for two-server PAKE are either symmetric in the sense that two peer servers equally contribute to the authentication or asymmetric in the sense that one server authenticates the client with the help of another server. This paper presents a symmetric solution for two-server PAKE, where the client can establish different cryptographic keys with the two servers, respectively. Our protocol runs in parallel and is more efficient than existing symmetric two-server PAKE protocol, and even more efficient than existing asymmetric two-server PAKE protocols in terms of parallel computation.

Partition enforcement policy is essential in the cache partition, and its main function is to protect the lines and retain the cache quota of each core. This paper focuses online protection based on its generation time rather than the CPU core ID that it belongs to or the position of the replacement stack, where it is located. The basic idea is that when a line is live, it must be protected and retained in the cache; when the line is “dead,” it needs to be evicted as early as possible. Therefore, the live-time protected counter (LvtP, four bits) is augmented to trace the lines' live time. Moreover, dead blocks are predicted according to the access event sequence. This paper presents a pseudopartition approach-LvtPPP and proposes a two-cascade victim selection mechanism to alleviate dead blocks based on the LRU replacement policy and the LvtP counter. LvtPPP also supports flexible handling of allocation deviation by introducing a parameter λ to adjust the generation time of the line. There is significant improvement of the performance and fairness in LvtPPP over PIPP and UCP according to the evaluation results based on Simics.

Design patterns for parallel computing attempt to make the field accessible to nonexperts by generalizing the common techniques experts use to develop parallel software. Existing parallel patterns have tremendous descriptive power, but it is often unclear to nonexperts how to choose a pattern based on the specific performance goals of a given application. This paper addresses the need for a pattern selection methodology by presenting four patterns and an accompanying decision framework for choosing from these patterns given an application's throughput and latency goals. The patterns are based on recognizing that one can partition an application's data or instructions and that these partitionings can be done in time or space, hence we refer to them as spatiotemporal partitioning strategies. This paper introduces a taxonomy that describes each of the resulting four partitioning strategies and presents a three-step methodology for selecting one or more given a throughput and latency goal. Several case studies are presented to illustrate the use of this methodology. These case studies cover several simple examples as well as more complicated applications including a radar processing application and an H.264 video encoder.

Cyber security is becoming an area of growing concern in the electric power industry with the development of smart grid. False data injection attack, which is against state estimation through SCADA network, has recently attracted wide research interests. This paper further develops the concept of load redistribution (LR) attack, a special type of false data injection attack. The damage of LR attacks to power system operations can manifest in an immediate or a delayed fashion. For the immediate attacking goal, we show in this paper that the most damaging attack can be identified through a max-min attacker-defender model. Benders decomposition within a restart framework is used to solve the bilevel immediate LR attack problem with a moderate computational effort. Its effectiveness has been validated by the Karush-Kuhn-Tucker (KKT)-based method solution in our previous work. For the delayed attacking goal, we propose a trilevel model to identify the most damaging attack and transform the model into an equivalent single-level mixed-integer problem for final solution. In summary, this paper enables quantitative analysis of the damage of LR attacks to power system operations and security, and hence provides an in-depth insight on effective attack prevention when resource budgets are limited. A 14-bus system is used to test the correctness of the proposed model and algorithm.

A major part of the design process for Integrated Circuits (IC) is the process of circuit verification, in which the correctness of a circuit's design is evaluated. Discrete event simulation is a central tool in this effort. As proscribed by Moore's law, the number of transistors which can be placed on an IC doubles every 18 months. As a result, simulation has become the major bottleneck in the circuit design process. To alleviate this difficulty, it is possible to make use of parallel (or distributed) circuit simulation. In this paper, we make use of a parallel gate-level simulator which we developed and which is based upon Time Warp. Gate-level simulations exhibit two characteristics which can easily result in either instability or severely degraded simulation performance. Because of the low computational granularity of a gate-level simulation and because the computational load varies throughout the course of the simulation, the performance of Time Warp can be either severely degraded or be unstable. Restraining the optimism of Time Warp via a bounded window and utilizing dynamic load balancing are approaches to deal with these difficulties. In this paper, we make use of learning techniques from artificial intelligence (multiagent Q-learning, simulated annealing) to develop a combined bounded window and dynamic load balancing algorithm for parallel digital logic simulation. We evaluated the performance of these algorithms on open source Sparc and Leon designs and on two Viterbi decoder designs. We observed up to 60 percent improvement in simulation time of one of the decoders using this approach.

Read-copy update (RCU) is a synchronization technique that often replaces reader-writer locking because RCU's read-side primitives are both wait-free and an order of magnitude faster than uncontended locking. Although RCU updates are relatively heavy weight, the importance of read-side performance is increasing as computing systems become more responsive to changes in their environments. RCU is heavily used in several kernel-level environments. Unfortunately, kernel-level implementations use facilities that are often unavailable to user applications. The few prior user-level RCU implementations either provided inefficient read-side primitives or restricted the application architecture. This paper fills this gap by describing efficient and flexible RCU implementations based on primitives commonly available to user-level applications. Finally, this paper compares these RCU implementations with each other and with standard locking, which enables choosing the best mechanism for a given workload. This work opens the door to widespread user-application use of RCU.

This paper develops a software service for dynamic performance optimization and control in performance-sensitive systems. The next generation of performance-sensitive systems is expected to be more distributed and dynamic. They will have multiple "knobs” that affect performance and resource allocation. However, relying on the conglomeration of independent knob controls can become increasingly suboptimal. The problem lies in performance composability or lack thereof; a challenge that arises because individual optimizations in performance-sensitive systems generally do not compose well when combined. Performance adaptation in such systems needs to be carefully designed and implemented by holistically considering performance composability in order to achieve desired system performance. A flexible supporting software layer is therefore needed to easily apply different holistic performance management techniques. In this paper, we develop a software service, called OptiTuner, that monitors the current performance and the resource availability in performance-sensitive systems and allows easy implementation of different performance management schemes based on theoretical concepts of constrained optimization and feedback control. In order to show the efficacy of OptiTuner, we apply it to implement three holistic energy minimization techniques in a real-time web server farm comprising 18 machines. Using an industry standard e-Business benchmark, TPC-W, we demonstrate that the three approaches save up to 40 percent of total energy cost compared to the baseline approaches that do not holistically optimize the cost.

This paper presents a scalable and adaptive decentralized metadata lookup scheme for ultralarge-scale file systems (more than Petabytes or even Exabytes). Our scheme logically organizes metadata servers (MDSs) into a multilayered query hierarchy and exploits grouped Bloom filters to efficiently route metadata requests to desired MDSs through the hierarchy. This metadata lookup scheme can be executed at the network or memory speed, without being bounded by the performance of slow disks. An effective workload balance method is also developed in this paper for server reconfigurations. This scheme is evaluated through extensive trace-driven simulations and a prototype implementation in Linux. Experimental results show that this scheme can significantly improve metadata management scalability and query efficiency in ultralarge-scale storage systems.

(A short version of this paper appears in IEEE INFOCOM 2009: http://www.research.ibm.com/people/i/iyengar/INFOCOM2009-kanon.pdf.) Peer-to-peer VoIP (voice over IP) networks, exemplified by Skype, are becoming increasingly popular due to their significant cost advantage and richer call forwarding features than traditional public switched telephone networks. One of the most important features of a VoIP network is privacy (for VoIP clients). Unfortunately, most peer-to-peer VoIP networks neither provide personalization nor guarantee a quantifiable privacy level. In this paper, we propose novel flow analysis attacks that demonstrate the vulnerabilities of peer-to-peer VoIP networks to privacy attacks. We then address two important challenges in designing privacy-aware VoIP networks: Can we provide personalized privacy guarantees for VoIP clients that allow them to select privacy requirements on a per-call basis? How to design VoIP protocols to support customizable privacy guarantee? This paper proposes practical solutions to address these challenges using a quantifiable k-anonymity metric and a privacy-aware VoIP route setup and route maintenance protocols. We present detailed experimental evaluation that demonstrates the performance and scalability of our protocol, while meeting customizable privacy guarantees.

Media streaming is expected to be one of the most promising services in mobile environments. Effective data streaming management techniques are, therefore, in strong demand. In an earlier paper, the ideas and benefits of two-level cooperative media streaming with headlight prefetching and dynamic chaining were demonstrated. Though complementary to each other, they operate in session-wide static and distinctive modes. Moreover, users do not have control over the quality and cost levels of the streaming services. The performance degradation or cost increment can reach an unacceptable level under fast or highly unstable moving patterns. In this paper, we propose the QoS-based dynamic adaptation techniques for the flexible employment and smooth integration of headlight prefetching and dynamic chaining to continuously provide quality streaming services to mobile users. The QoS-aware dynamic headlight prefetching is for the cooperation between streaming access points to dynamically adjust the prefetching scheme in response to the fast changing moving patterns. Adaptive P2P media streaming is for the cooperation between mobile users such that multiple peers can be used as streaming sources to increase the likelihood of successful chaining. Furthermore, a QoS-based technique is developed to dynamically trigger and proportionally adjust the prefetching degree when the stability and quality of P2P streaming service vary. With extensive simulation and performance evaluation, we demonstrate that the proposed dynamic adaptation techniques significantly improve the service quality and streaming performance of cooperative media streaming in mobile environments.

With the development of cloud computing, more and more data owners are motivated to outsource their documents to the cloud and share them with the authorized data users securely and flexibly. To protect data privacy, the documents are generally encrypted before being outsourced to the cloud and hence their searchability decreases. Though many privacy-preserving document search schemes have been proposed, they cannot reach a proper balance among functionality, flexibility, security and efficiency. In this paper, a new encrypted document retrieval system is designed and a proxy server is integrated into the system to alleviate data owner's workload and improve the whole system's security level. In this process, we consider a more practical and stronger threat model in which the cloud server can collude with a small number of data users. To support multiple document search patterns, we construct two AVL trees for the filenames and authors, and a Hierarchical Retrieval Features tree (HRF tree) for the document vectors. A depth-first search algorithm is designed for the HRF tree and the Enhanced Asymmetric Scalar-Product-Preserving Encryption (Enhanced ASPE) algorithm is utilized to encrypt the HRF tree. All the three index trees are linked with each other to efficiently support the search requests with multiple parameters. Theoretical analysis and simulation results illustrate the security and efficiency of the proposed framework.

It has been widely acknowledged that online file hosting systems within the “cloud” of the Internet have provided valuable services to end users who wish to share files of any size. Such online hosting services are typically provided by dedicated servers, either in content distribution networks (CDNs) or large data centers. Server bandwidth costs, however, are prohibitive in these cases, especially when serving large volumes of files to a large number of users. Though it seems intuitive to take advantage of peer upload bandwidth to mitigate such server bandwidth costs in a complementary fashion, it is not trivial to design and fine-tune important aspects of such peer-assisted online hosting in a real-world large-scale deployment. This paper presents FS2You, a large-scale and real-world online file hosting system with peer assistance and semipersistent file availability. FS2You is designed to dramatically mitigate server bandwidth costs. In this paper, we show a number of key challenges involved in such a design objective, our architectural and protocol design in response to these challenges, as well as an extensive measurement study at a large scale to demonstrate the effectiveness of our design, using real-world traces that we have collected. To our knowledge, this paper represents the first attempt to design, implement, and evaluate a new peer-assisted semipersistent online file hosting system at a realistic scale. Since the launch of FS2You, it has quickly become one of the most popular online file hosting systems in mainland China, and a favorite in many online forums across the country.

In the past few years, P2P file distribution applications (e.g., BitTorrent) are becoming so popular that they are the dominating source of Internet traffic. This creates significant problems to Internet Service Providers (ISPs), not only because of the added complexity in traffic engineering, but the increase of traffic, in particular on the cross-ISP links, implies congestion and a higher operating cost. In this paper, we consider an ISP-friendly file distribution protocol which uses the “exploiting-the-locality principle” (ELP) to reduce the cross-ISP traffic. To show its benefit, we derive an upper and lower bound of cross-ISP traffic for the protocols which rely on ELP and show that the cross-ISP traffic can be reduced significantly when the number of peers within an ISP increases. To carry out realistic study, we design and implement our ISP-friendly protocol (which is compatible with the current BitTorrent protocol) and carry out large scale experiments on PlanetLab to measure the reduction of the cross ISP-traffic and the file downloading time. More important, we also show how the proposed ISP-friendly protocol can handle the “black-hole” security attack. This paper sheds light on the merits and design direction of ISP-friendly content distribution protocols.

Intrusion Detection Systems (IDSs) are a major line of defense for protecting network resources from illegal penetrations. A common approach in intrusion detection models, specifically in anomaly detection models, is to use classifiers as detectors. Selecting the best set of features is central to ensuring the performance, speed of learning, accuracy, and reliability of these detectors as well as to remove noise from the set of features used to construct the classifiers. In most current systems, the features used for training and testing the intrusion detection systems consist of basic information related to the TCP/IP header, with no considerable attention to the features associated with lower level protocol frames. The resulting detectors were efficient and accurate in detecting network attacks at the network and transport layers, but unfortunately, not capable of detecting 802.11-specific attacks such as deauthentication attacks or MAC layer DoS attacks. In this paper, we propose a novel hybrid model that efficiently selects the optimal set of features in order to detect 802.11-specific intrusions. Our model for feature selection uses the information gain ratio measure as a means to compute the relevance of each feature and the k-means classifier to select the optimal set of MAC layer features that can improve the accuracy of intrusion detection systems while reducing the learning time of their learning algorithm. In the experimental section of this paper, we study the impact of the optimization of the feature set for wireless intrusion detection systems on the performance and learning time of different types of classifiers based on neural networks. Experimental results with three types of neural network architectures clearly show that the optimization of a wireless feature set has a significant impact on the efficiency and accuracy of the intrusion detection system.

In this paper, we address attacks that exploit the timing behavior of TCP and other protocols and applications in low-latency anonymity networks. Mixes have been used in many anonymous communication systems and are supposed to provide countermeasures to defeat traffic analysis attacks. In this paper, we focus on a particular class of traffic analysis attacks, flow-correlation attacks, by which an adversary attempts to analyze the network traffic and correlate the traffic of a flow over an input link with that over an output link. Two classes of correlation methods are considered, namely time-domain methods and frequency-domain methods. Based on our threat model and known strategies in existing mix networks, we perform extensive experiments to analyze the performance of mixes. We find that all but a few batching strategies fail against flow-correlation attacks, allowing the adversary to either identify ingress and egress points of a flow or to reconstruct the path used by the flow. Counterintuitively, some batching strategies are actually detrimental against attacks. The empirical results provided in this paper give an indication to designers of Mix networks about appropriate configurations and mechanisms to be used to counter flow-correlation attacks.

A distinct trend has emerged that the Internet is used to transport data on a more and more massive scale. Capacity shortage in the backbone networks has become a genuine possibility, which will be more serious with fiber-based access. The problem addressed in this paper is how to conduct massive content distribution efficiently in the future network environment, where the capacity limitation can equally be at the core or the edge. We propose a novel technique as a main content transport mechanism to achieve efficient network resource utilization. The technique uses multiple trees for distributing different file pieces, which at the heart is a version of swarming. In this paper, we formulate an optimization problem for determining an optimal set of distribution trees as well as the rate of distribution on each tree under bandwidth limitation at arbitrary places in the network. The optimal solution can be found by a distributed algorithm. The results of the paper not only provide stand-alone solutions to the massive content distribution problem, but should also help the understanding of existing distribution techniques such as BitTorrent or FastReplica.

Layered streaming in P2P networks has become a hot topic recently. However, the "layered" feature makes the data scheduling quite different from that for nonlayered streaming, and it hasn't been systematically studied yet. In this paper, first, according to the unique characteristics caused by layered coding, we present four objectives that should be addressed by scheduling: throughput, layer delivery ratio, useless packets ratio, and subscription jitter prevention; then a three-stage scheduling approach LayerP2P is designed to request data, where the min-cost flow model, probability decision mechanism, and multiwindow remedy mechanism are used in Free Stage, Decision Stage, and Remedy Stage, respectively, to collaboratively achieve the above objectives. With the basic version of LayerP2P and corresponding experiment results achieved in our previous work, in this paper, more efforts are put on its mechanism details and analysis to its unique features; besides, to further guarantee the performance under sharp bandwidth variation, we propose the enhanced approach by improving the Decision Stage strategy. Extensive experiments by simulation and real network implementation indicate that it outperforms other schemes. LayerP2P has also been deployed in PDEPS Project in China, which is expected to be the first practical layered streaming system for education in P2P networks.

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using ternary content addressable memories (TCAMs) to perform high-speed packet classification has become the de facto standard in the industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known interval expansion problem. As packet classification rules usually have fields specified as intervals, converting such rules to TCAM-compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules means more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers have been increasing rapidly with the growing number of services deployed on the Internet. In this paper, we propose to address the interval expansion problem of TCAMs by removing redundant rules in classifiers. This equivalent transformation can significantly reduce the number of TCAM entries needed by a classifier. Our experiments on real-life classifiers show an average reduction of 58.2 percent in the number of TCAM entries by removing redundant rules. Given the logical interleaving nature of packet filtering rules, identifying redundant rules in classifiers is by no means trivial, and to achieve the guarantee of no redundant rules in resulting classifiers is even more challenging. In this paper, for the first time, we give a necessary and sufficient condition for identifying all redundant rules in a classifier. Based on this condition, we categorize redundant rules into upward redundant rules and downward redundant rules. Second, we present two algorithms for detecting and removing the two types of redundant rules, respectively. Third, we formally prove that the resulting classifiers have no redundant rules after running the two algorithms. Last, we conduct extensive experiments on both real-life and synthetic classifiers. The experimental results show that our redundancy removal algorithms are both effective and efficient.

This paper presents a queuing model to evaluate the latency associated with file transfers or replications in peer-to-peer (P2P) computer systems. The main contribution of this paper is a modeling framework for the peers that accounts for the file size distribution, the search time, load distribution at peers, and number of concurrent downloads allowed by a peer. We propose a queuing model that models the nodes or peers in such systems as M/G/1/K processor sharing queues. The model is extended to account for peers which alternate between online and offline states. The proposed queuing model for the peers is combined with a single class open queuing network for the routers interconnecting the peers to obtain the overall file transfer latency. We also show that in scenarios with multipart downloads from different peers, a rate proportional allocation strategy minimizes the download times.

Thread-level parallelism (TLP) has been extensively studied in order to overcome the limitations of exploiting instruction-level parallelism (ILP) on high-performance superscalar processors. One promising method of exploiting TLP is dynamic speculative multithreading (D-SpMT), which extracts multiple threads from a sequential program without compiler support or instruction set extensions. This paper introduces Cascadia, a D-SpMT multicore architecture that provides multigrain thread-level support and is used to evaluate the performance of several benchmarks. Cascadia applies a unique sustainable IPC (sIPC) metric on a comprehensive loop tree to select the best performing nested loop level to multithread. This paper also discusses the relationships that loops have on one another, in particular, how loop nesting levels can be extended through procedures. In addition, a detailed study is provided on the effects that thread granularity and interthread dependencies have on the entire system.

In attempts to exploit a diverse set of resources in grids efficiently, numerous assays in resource management, particularly scheduling, have been made. The primary objective of these efforts is the minimization of application completion time; however, they tend to achieve this objective at the expense of redundant resource usage. This paper investigates the problem of scheduling workflow applications on grids and presents a novel scheduling algorithm for the solution of this problem. Our algorithm performs the scheduling by accounting for both completion time and resource usage-dual objectives. Since the performance of grid resources changes dynamically and the accurate estimation of their performance is very difficult, our algorithm incorporates rescheduling to deal with unforeseen performance fluctuations effectively. The paper provides a comparative evaluation study conducted by using an extensive set of experiments. The study demonstrates that the proposed algorithm delivers promising performance in three respects: completion time, resource utilization, and robustness to resource-performance fluctuations.

The emergence of scientific applications that produce huge volume of data files requires special attention, and leads to the problem of how to manage and share such data files in wide area properly. In large-scale Grid, data replication provides a suitable solution for managing data files where data reliability and data availability are enhanced. Replica selection is one of the major functions of data replication that decides which replica location is the best for Grid users. In this paper, we address the replica selection problem in a Grid environment where the users are competing for the limited data resource. Thus, our aim is to establish fairness among the users in the selection decisions. Since the criteria that play a role in the selection process conflict with each other and produce heterogeneous values, the Analytical Hierarchy Process is used to solve this optimization problem. The proposed system validity and performance are evaluated by using a simulation. The simulation results were produced and discussed in this paper.

In this paper we revisit the supernode-shape selection problem, that has been widely discussed in bibliography. In general, the selection of the supernode transformation greatly affects the parallel execution time of the transformed algorithm. Since the minimization of the overall parallel execution time via an appropriate supernode transformation is very difficult to accomplish, researchers have focused on scheduling-aware supernode transformations that maximize parallelism during the execution. In this paper we argue that the communication volume of the transformed algorithm is an important criterion, and its minimization should be given high priority. For this reason we define the metric of the per process communication volume and propose a method to minimize this metric by selecting a communication-aware supernode shape. Our approach is equivalent to defining a proper Cartesian process grid with MPI_Cart_Create, which means that it can be incorporated in applications in a straightforward manner. Our experimental results illustrate that by selecting the tile shape with the proposed method, the total parallel execution time is significantly reduced due to the minimization of the communication volume, despite the fact that a few more parallel execution steps are required.