IEEE Transactions on Parallel and Distributed Systems

PrePrint: Anchor-Free Localization though Flip Error Resistant Map Stitching in Wireless Sensor Network

In patch-and-stitch localization algorithms, flip-error refers to the kind of error in which a patch is stitched to the map as being wrongly reflected. In this paper, we present an anchor-free localization algorithm which tries to detect and prevent flip errors. The flip error prevention is achieved by two filtering mechanisms: the flipambiguity test and the flip-conflict detection. Based on two techniques, we devised an anchor-free localization algorithm and evaluated the performance of the proposed algorithm though simulations. The results show that our algorithm achieves significant performance improvements over the existing algorithms.

PrePrint: Logoot-Undo: Distributed Collaborative Editing System on P2P Networks

Peer-to-peer systems provide scalable distribution of content for cheap and resist to censorship attempts. However, P2P networks mainly distribute immutable contents and provide poor support for highly dynamic contents produced by collaborative systems. A new class of algorithms called CRDT (Commutative Replicated Data Type) are emerging for ensuring consistency of highly dynamic content on P2P networks. However, if existing CRDT algorithms support the "edit anywhere, anytime" feature, they do not support the "undo anywhere, anytime" feature. In this paper, we present the Logoot-Undo CRDT algorithm that integrates the "undo anywhere, anytime" feature. We compare the performance of the proposed algorithm with related algorithms and measure the impact of the undo feature on the global performance of the algorithm. We prove that the cost of the undo feature remains low on a corpus of data extracted from Wikipedia.

PrePrint: A High-Performance Heterogeneous Computing Platform for Biological Sequence Analysis

Advances in bioinformatics research continue to add complexity to the analyses and interpretation of biological data. Certain sequence database searches may take weeks to complete due to complicated data dependencies by dynamic programming. A reconfigurable coprocessor can remove this computational bottleneck and accelerate the operation. This paper presents a heterogeneous computing platform through Message Passing Interface (MPI) enabled enterprise computing infrastructure for high-throughput biological sequence analysis. The computing platform integrates heterogeneous computer architectures including conventional processors with Streaming Single Instruction Multiple Data Extensions 2 (SSE2) instructions, reconfigurable coprocessors, and legacy processors together into one system, and allows each to perform the task to which it is best suited. With appropriate computation and communication scheduling, the integrated heterogeneous computing infrastructure is designed to accommodate various types of accelerators to provide a High Performance Computing (HPC) framework to support the most widely used life science applications.

PrePrint: Semantics Based Object Caching in Distributed Systems

In order to utilize the semantics of object methods to ensure cached object consistency, method group commutativity specifies the conditions under which a group of methods will commute. Method group commutativity is determined using a semantic specification of object methods, provided in terms of logical expressions, to create commutativity conjectures that are analyzed using the PVS theorem prover. This analysis results in the creation of a method commutativity specification (MCS) which is used by a distributed caching system to ensure the consistency of method invocations. For greater commutativity, weaker consistency requirements can be specified in the MCS. This base approach is enhanced by optimizations that consider a client's sequential execution of methods and that reduce the amount of data cached by the client. The effectiveness of method group commutativity and associated optimizations is evaluated using Java RMI application benchmarks.

IEEE Transactions on Parallel and Distributed Systems - April 2010 (Vol. 21, No. 4)

IEEE Transactions on Parallel and Distributed Systems

PrePrint: A Direct Coherence Protocol for Many-Core Chip Multiprocessors

Future many-core CMP designs that will integrate tens of processor cores on-chip will be constrained by area and power. Area constraints make impractical the use of a bus or a crossbar as the on-chip interconnection network, and tiled CMPs organized around a direct interconnection network will probably be the architecture of choice. Power constraints make impractical to rely on broadcasts (as, for example, Token-CMP does) or any other brute-force method for keeping cache coherence, and directory-based cache coherence protocols are currently being employed. Unfortunately, directory protocols introduce indirection to access directory information, which negatively impacts performance. In this work, we present DiCo-CMP, a novel cache coherence protocol especially suited to future many-core tiled CMP architectures. In DiCo-CMP the task of storing up-to-date sharing information and ensuring ordered accesses for every memory block is assigned to the cache that must provide the block on a miss. Therefore, DiCo-CMP reduces the miss latency compared to a directory protocol by sending requests directly to the cache that provides the block in a cache miss. These latency reductions result in improvements in execution time of up to 6% on average over a directory protocol. In comparison with Token-CMP, our protocol only sends one request message for each cache miss, as such is able to reduce network traffic by 43%.

PrePrint: Mobility-Assisted Spatiotemporal Detection in Wireless Sensor Networks

Wireless sensor networks (WSNs) deployed for mission-critical applications face the fundamental challenge of meeting stringent spatiotemporal performance requirements using nodes with limited sensing capacity. Although advance network planning and dense node deployment may initially achieve the required performance, they often fail to adapt to the unpredictability and variability of physical reality. This paper explores efficient use of mobile sensors to address limitations of static WSNs for target detection. We propose a data fusion based detection model that enables static and mobile sensors to effectively collaborate in target detection. An optimal sensor movement scheduling algorithm is developed to minimize the total moving distance of sensors while achieving a set of spatiotemporal performance requirements including high detection probability, low system false alarm rate and bounded detection delay. The effectiveness of our approach is validated by extensive simulations based on real data traces collected by 23 sensor nodes

PrePrint: On Improving Parallelized Network Coding with Dynamic Partitioning

In this paper, we investigate parallel implementation techniques for network coding. It is known that network coding is useful for both wired and wireless networks and it also mitigates peer/piece selection problems in P2P file sharing systems. However, due to the decoding complexity of network coding, there have been concerns about adoption of network coding in practical network systems and to improve the decoding speed with the exploitation of parallelism has been proposed previously. In this paper, we argue that naive parallelization strategies of network coding may result in unbalanced workload distribution and thus limiting performance improvements. We further argue that higher performance enhancement can be achieved through balanced partitioning methods in parallelized network coding and propose new parallelization techniques for network coding. Our experiments show that, on a quad-core processor system, proposed algorithms exhibit up to 5.69 speed-up which is better than the linear speed-up with the influence of additional cache. Moreover, on an octal-core system, our algorithms even achieve speed-up of 8.46 compared to a sequential network coding and 43.3% faster than an existing parallelized technique using 1 Mbytes data with 1024 × 1024 coefficient matrix size.

PrePrint: Empirical Evaluation of Wireless Localization When Using Multiple Antennas

We show that signal strength variability can be reduced by employing multiple low-cost antennas at fixed locations. We further explore the impact of this reduction on wireless localization by analyzing a representative set of algorithms ranging from fingerprint matching, to statistical maximum likelihood estimation, to threshold bounding of signal fingerprints, and to multilateration. Using an indoor wireless testbed, we provide experimental evaluation of the localization performance under multiple antennas. We found that in nearly all cases the performance of localization algorithms improved when using multiple antennas. Specifically, the median and the 90th percentile error can be reduced up to 70%. Additionally, we found that multiple antennas improve the localization stability significantly, up to 100% improvement, when there are small scale 3-dimensional movements of a mobile device around a given location.

PrePrint: ILBO: Balance Inbound Traffic Dynamically in Multi-homed Stub Networks

Multihoming load balancing improves network performance and makes better use of network resource by leveraging the traffic among the access links in a multi-homed network. Currently, no effective load balancing system is available to handle the inbound traffic in a multi-homed stub network, where the traffic volume is unknown to the network and the route of the traffic is hard to control. In this paper, we propose ILBO, an inbound traffic load balancing mechanism to effectively balance the inbound traffic in a multi-homed stub network. ILBO predicts and schedules the inbound traffic based on outbound traffic. It adopts a two step traffic predictor to increase the prediction accuracy and also provides an inbound traffic control scheme that can guarantee the successful execution of the traffic scheduling. We have evaluated the effectiveness of ILBO in a trace driven simulation with real world traffic traces collected from multi-homed stub networks.

PrePrint: Design and Deployment of Sensor Network for Real-time High-fidelity Volcano Monitoring

This paper presents the design and deployment experience of an air-dropped wireless sensor network for volcano hazard monitoring. The deployment of five stations into the rugged crater of Mount St. Helens only took one hour with a helicopter. The stations communicate with each other through an amplified 802:15:4 radio and establish a self-forming and self-healing multi-hop wireless network. The distance between stations is up to 2 km. Each sensor station collects and delivers real-time continuous seismic, infrasonic, lightning, GPS raw data to a gateway. The main contribution of this paper is the design and deployment of a robust sensor network to replace data loggers and provide real-time long-term volcano monitoring. The system supports UTC-time synchronized data acquisition with 1ms accuracy, and is online configurable. It has been tested in the lab environment, the outdoor campus and the volcano crater. Despite the heavy rain, snow, and ice as well as gusts exceeding 120 miles per hour, the sensor network has achieved a remarkable packet delivery ratio above 99% with an overall system uptime of about 93:8% over the 1:5 months evaluation period after deployment. Our initial deployment experiences with the system have alleviated the doubts of domain scientists and prove to them that a low-cost sensor network system can support real-time monitoring in extremely harsh environments.

PrePrint: Sensor-Mission Assignment in Constrained Environments

When a sensor network is deployed in the field it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this article, we consider new sensor-assignment problems motivated by frugality, i.e., the conservation of resources, for both static and dynamic settings. In the most general setting, the problems we study are NP-hard even to approximate, and so we focus on heuristic algorithms that perform well in practice. In the static setting, we propose a greedy centralized solution and a more sophisticated solution that uses the Generalized Assignment Problem model and can be implemented in a distributed fashion. In the dynamic setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We find that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help, making this decision based on the value of the mission, the sensor's remaining energy, and (if known) the remaining target lifetime of the network. Finally, we evaluate our solutions through simulations.

PrePrint: Performance Evaluation of gLite Grids through GSPNs

Grid Computing supports the shared and coordinated use of several resources in dynamic Virtual Organizations. In the last few years, it is evolving into a business-innovating technology that is driving commercial adoption. Such a new scenario calls for powerful strategies able to guarantee stringent QoS requirements in order to meet Service Level Agreements (SLAs) between customers and providers. For this reason, it is necessary to analyze and predict performance with respect to different load conditions or management strategies. In this paper, we present a methodology to analyze performance in gLite Grids through the use of Generalized Stochastic Petri Nets (GSPNs). We introduce a cluster-level model of a typical gLite site taking into account the coexistence between normal and MPI-based jobs. We investigate the influence of different strategies (e.g., scheduling) on the performance of the whole site, highlighting aspects related to both customer and provider point-of-views. We also provide a business-oriented performance analysis introducing two different SLA typologies and highlighting how the site configuration may influence the expected profit of the service provider.

PrePrint: Maximizing Service Reliability in Distributed Computing Systems with Random Node Failures: Theory and Implementation

In distributed computing systems (DCSs) where server nodes can fail permanently with non-zero probability, the system performance can be assessed by means of the service reliability, defined as the probability of serving all the tasks queued in the DCS before all the nodes fail. This paper presents a rigorous probabilistic framework to analytically characterize the service reliability of a DCS in the presence of communication uncertainties and stochastic topological changes due to node deletions. The framework considers a system composed of heterogeneous nodes with stochastic service and failure times and a communication network imposing random tangible delays. The framework also permits arbitrarily specified, distributed load-balancing actions to be taken by the individual nodes in order to improve the service reliability. The presented analysis is based upon a novel use of the concept of stochastic regeneration, which is exploited to derive a system of difference-differential equations characterizing the service reliability. The theory is further utilized to optimize certain load-balancing policies for maximal service reliability; the optimization is carried out by means of an algorithm that scales linearly with the number of nodes in the system. The analytical model is validated using both Monte-Carlo simulations and experimental data collected from a DCS testbed.

PrePrint: Efficient and Robust Schemes for Sensor Data Aggregation Based on Linear Counting

Sensor networks have received considerable attention in recent years, and are employed in the applications where data are expensive to collect. In these applications, statistical aggregates over the readings of a group of sensor nodes are often needed. To conserve resources for sensor nodes, in-network strategies are adopted to process the aggregates. One primitive in-network aggregation strategy is the tree-based aggregation, where the aggregates are computed along a spanning tree over a sensor network. However, a shortcoming with the tree-based aggregation is that it is not robust against communication failures, which are common in sensor networks. One of the solutions to overcome this shortcoming is to enable multi-path routing, by which each node broadcasts its reading to multiple neighbors. However, multi-path routing based aggregation suffers from the problem of overcounting sensor readings. This paper proposes two schemes based on linear counting technique to deal with the overcounting problem. These two schemes process aggregates by statically and dynamically, respectively, allocating space for the use of the linear counting technique. Both schemes provide the same accuracy guarantee but involve different communication costs. Through extensive experiments, we demonstrate the performance of using these two schemes as solutions for processing aggregates in sensor networks.

PrePrint: A Distributed Approach of Proportional Bandwidth Allocation for Real-Time Services in UltraWideBand (UWB) WPANs

Quality of service (QoS) provisioning is one of the most important criteria in newly emerging UWB WPANs. Recently, the WiMedia Alliance has announced the PHY/MAC specification for UWB WPANs. The WiMedia MAC uses the contention-free reservation-based access, which supports isochronous traffic with distributed reservation protocol, and the contention-based access, which provides service differentiation for best-effort and variable-rate real-time traffic with prioritized channel access, similar to the EDCA in IEEE 802.11e. In this paper, we conduct a comprehensive theoretical analysis and show that with the currently recommended parameter setting, EDCA cannot provide adequate QoS. In particular, EDCA cannot allocate bandwidth in a deterministic proportional manner and the system bandwidth is under-utilized. After identifying the deficiency of EDCA, we propose an enhanced QoS-provisioning framework for the PCA scheme that dynamically controls channel access to adjust allocated bandwidth depending on the change of application's bit rate. We show that in this framework, 1) variable-rate real-time traffic is adaptively guaranteed of deterministic bandwidth via a contention-based reservation access method; 2) best-effort traffic is provided with deterministic proportional QoS; 3) the bandwidth utilization is maximized. We have also validated and evaluated the QoS-provisioning capability of the proposed PCA framework both via simulation and empirical study.

PrePrint: MIMO Power Control for High-Density Servers in an Enclosure

Power control is becoming a key challenge for effectively operating a modern data center. In addition to reducing operating costs, precisely controlling power consumption is an essential way to avoid system failures caused by power capacity overload or overheating due to increasing high server density. Control-theoretic techniques have recently shown a lot of promise for power management because of their better control performance and theoretical guarantees on control accuracy and system stability. However, existing work oversimplifies the problem by controlling a single server independently from others. As a result, at the enclosure level where multiple high-density servers are correlated by common workloads and share common power supplies, power cannot be shared to improve application performance. In this paper, we propose an enclosure-level power controller that shifts power among servers based on their performance needs, while controlling the total power of the enclosure to be lower than a constraint. Our controller features a rigorous design based on an optimal Multi-Input-Multi-Output (MIMO) control theory. We present detailed control problem formulation and transformation to a standard constrained least-squares problem, as well as stability analysis in the face of significant workload variations. We then conduct extensive experiments on a physical testbed to compare our controller with three state-of-the-art controllers. Our empirical results demonstrate that our controller outperforms all the three baselines by having more accurate power control and up to 11.8% better benchmark performance.

PrePrint: Twisted Torus Topologies for Enhanced Interconnection Networks

Many current parallel computers are built around a torus interconnection network. Machines from Cray, HP and IBM, among others, make use of this topology. In terms of topological advantages, square (2D) or cubic (3D) tori would be the topologies of choice. However, for different practical reasons, 2D and 3D tori with different number of nodes per dimension have been used. These mixed-radix topologies are not edge-symmetric, which translates into poor performance due to an unbalanced use of network resources. In this work, we analyze twisted 2D and 3D mixed-radix tori that remove the network bottlenecks present in non-twisted ones. Such topologies recover edge-symmetry and, consequently, balance the utilization of their links. The distance-related properties of twisted tori together with a full characterization of their bisection bandwidth are described in this paper. A simulation-based performance evaluation has been carried out in order to asses the network performance under synthetic and trace-driven workloads. The obtained results show noticeable and consistent performance gains (up to an increase of 74% in accepted load). In addition, we propose scalable and practicable packet routing mechanisms and wiring layouts for these interconnection systems. The complexity of the resulting architectural proposals is similar to the one exhibited by traditional routing and folding mechanisms in standard tori.

PrePrint: A Distributed Efficient Flow Control Scheme for Multi-Rate Multicast Networks

This paper proposes a novel and efficient distributed flow control scheme for multi-rate multicast (MR-M), based on the well-known Proportional Integral and Derivative (PID) controllers. The PID controller at each router computes its expected incoming rate and feedbacks this rate to its upstream router, such that the local buffer occupancy can be stabilized at an appropriate value. We give the theoretical analysis of the proposed PID controller in terms of system stability. The proposed MR-M controller achieves the fairness in two aspects: 1) The intra-session fairness, i.e., the receivers from the same source within the same multicast session can receive data at different rates, if they subscribe networks with different capacities; 2) The inter-session fairness, i.e., the link bandwidth is fairly shared among multiple multicast sessions from different sources. Extensive simulations have been conducted and the results have demonstrated a superior performance of the proposed scheme in terms of system stability, high link utilization, and high throughput.

PrePrint: FS2You: Peer-Assisted Semi-Persistent Online Storage and Distribution at a Large Scale

Though online storage systems in the Internet have provided valuable services to share files among end users, such services are typically provided by dedicated servers with prohibitive server bandwidth costs as the systems scale up. It is intuitive, but non-trivial, to mitigate such costs by taking advantage of peer upload bandwidth in a complementary fashion. This paper presents FS2You, a large-scale and real-world online storage and distribution system with peer assistance and semi-persistent 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 semi-persistent online storage and distribution system at a realistic scale. Since the launch of FS2You, it has quickly become one of the most popular online storage and distribution systems in mainland China, and a favorite in many online forums across the country.

PrePrint: A Secure Decentralized Erasure Code for Distributed Networked Storage

Distributed networked storage systems provide the storage service on the Internet. We address the privacy issue of the distributed networked storage system. It is desired that data stored in the system remain private even if all storage servers in the system are compromised. The major challenge of designing these distributed networked storage systems is to provide a better privacy guarantee while maintaining the distributed structure. To achieve this goal, we introduce secure decentralized erasure code, which combines a threshold public key encryption scheme and a variant of the decentralized erasure code. Our distributed networked storage system constructed by the secure decentralized erasure code is decentralized, robust, private, and with low storage cost.

PrePrint: 2PASS: Bandwidth-Optimized Location Cloaking for Anonymous Location-Based Services

Protection of users' location privacy is a critical issue for location-based services. Location cloaking has been proposed to blur users' accurate locations with cloaked regions. Although various cloaking algorithms have been studied, none of the prior work has explored the impact of cloaking on the bandwidth usage of requested services. In this paper, we develop an innovative result-aware location cloaking approach, called 2PASS. Based on the notion of Voronoi cells, 2PASS minimizes the number of objects to request and hence the bandwidth while meeting the same privacy requirement. The core component of 2PASS is a lightweight WAG-tree index, based on which efficient and secure client and server procedures are designed. Through threat analysis and experimental results, we argue that 2PASS is robust and outperforms state-of-the-art approaches in terms of various metrics, such as query response time and bandwidth consumption. We also enclose a case study of 2PASS in a real-life application.

PrePrint: Group-Based Negotiations in P2P Systems

In P2P systems groups are typically formed to share resources and/or to carry on joint tasks. In distributed environments formed by a large number of peers conventional authentication techniques are inadequate for the group joining process, and more advanced ones are needed. Complex transactions among peers may require more elaborate interactions based on what peers can do or possess instead of peers' identity. In this work we propose a novel peer group joining protocol. We introduce a highly expressive resource negotiation language, able to support the specification of a large variety of conditions applying to single peers or groups of peers. Moreover, we define protocols to test such resource availability customized to the level of assurance required by the peers. Our approach has been tested and evaluated on an extension of the JXTA P2P platform. Our results show the robustness of our approach in detecting malicious peers, detected both during the negotiation and during the peer group lifetime. Regardless of the peer group cardinality and interaction frequency, the peers always detect possible free riders within a small time frame.

PrePrint: Fast and Message-Efficient Global Snapshot Algorithms for Large-Scale Distributed Systems

Large scale supercomputers and distributed systems such as peer-to-peer systems typically have a fully connected logical topology over a large number of processors. Existing snapshot algorithms in such systems have high response time and/or require a large number of messages, typically, $O(n^2)$, where $n$ is the number of processes. In this paper, we present a suite of two algorithms: {\em Simple\_Tree}, and {\em hypercube}, that are both fast and require a small number of messages. This makes the algorithms highly scalable. {\em Simple\_Tree} requires $O(n)$ messages and has $O(\log \,n)$ response time. {\em Hypercube} requires $O(n \, \log \, n)$ messages and has $O(\log \, n)$ response time, in addition to having the property that the roles of all the processes are symmetrical. Process symmetry implies greater potential for balanced workload and congestion-freedom. All the algorithms assume non-FIFO channels.

PrePrint: Distributed Network Formation for n-way Broadcast Applications

In an n-way broadcast application each one of n overlay nodes wants to push its own distinct large data file to all other n-1 destinations as well as download their respective data files. BitTorrent-like swarming protocols are ideal choices for handling such massive data volume transfers. The original BitTorrent targets one-to-many broadcasts of a single file to a very large number of receivers and thus, by necessity, employs a sub-optimized overlay topology. n-way broadcast applications on the other hand, owing to their inherent complexity, are realizable only in small to medium scale networks. In this paper, we show that we can leverage this scale constraint to construct optimized overlay topologies that take into consideration the end-to-end characteristics of the network and as a consequence deliver far superior performance compared to random and myopic (greedy) approaches. We present the Max-Min and Max-Sum peer-selection policies used by individual nodes to select their neighbors. The first one strives to maximize the available bandwidth to the slowest destination, while the second maximizes the aggregate output rate. We design a swarming protocol suitable for n-way broadcast and operate it on top of overlay graphs formed by nodes that employ Max-Min or Max-Sum policies. Using measurements from a PlanetLab prototype implementation and trace-driven simulations, we demonstrate that the performance of swarming protocols on top of our constructed topologies is far superior to the performance of random and myopic overlays.

PrePrint: Filter Design and Analysis in Frequency Domain for Server Scheduling and Optimization

The dynamics of Internet traffic greatly complicate the problem of server performance modeling and optimization. Most of the existing approaches study the interaction between the factors of server capacity, request scheduling, and service quality in the time domain. In this paper, we characterizes the relationship in a filter model.We present a design and analysis of the filter for general input traffic in the frequency domain. By the model, a server scheduler operates as an finite-duration impulse response (FIR) filter that transforms the request process into the workload process with the objective of minimizing the power leakage of the transformation. Most Internet traffic has monotonically decreasing power spectral density functions over frequency. For this type of input traffic, we prove that optimal schedulers must have a convex structure. Uniform resource allocation is an extreme case of the convexity and is proven to be optimal for traffic of independent arrivals. We integrate the convex-structural principle with GPS scheduling discipline and show that the enhanced GPS policy improves the service quality significantly. Furthermore, we show that long range dependency in the input traffic results in power shift from high frequency to lower frequency bands and consequently leads to an increase of power leakage in the transformation and a degradation of the service quality.

PrePrint: Robust Load Delegation in Service Grid Environments

In this paper, we address the problem of finding well-performing workload exchange policies for decentralized Computational Grids using an Evolutionary Fuzzy System. To this end, we establish a non-invasive collaboration model on the Grid layer which requires minimal information about the participating High Performance and High Throughput Computing (HPC/HTC) centers and which leaves the local resource managers completely untouched. In this environment of fully autonomous sites, independent users are assumed to submit their jobs to the Grid middleware layer of their local site, which in turn decides on the delegation and execution either on the local system or on remote sites in a situation-dependent, adaptive way. We find for different scenarios that the exchange policies show good performance characteristics not only with respect to traditional metrics such as average weighted response time and utilization, but also in terms of robustness and stability in changing environments.

PrePrint: On the Performance of Content Delivery Under Competition in a Stochastic Unstructured Peer-to-Peer Network

Peer-to-peer (P2P) network is widely used for transferring large files nowadays. In the literature, it has been often assumed that there is only one downloading peer in the network, ignoring the interaction and competition among peers. In this paper, we investigate the impact of the interaction and competition among peers on downloading performance under stochastic, heterogeneous, unstructured P2P settings, thereby greatly extending the existing results on stochastic P2P networks made only under a single downloading peer in the network. To analyze the average download time in a P2P network with multiple competing downloading peers, we first introduce the notion of system utilization tailored to a P2P network. We investigate the relationship between the average download time, system utilization and the level of competition among downloading peers in a stochastic P2P network. We then derive an achievable lower bound on the average download time and propose algorithms to give the peers the minimum average download time. Our result can much improve the download performance compared to earlier results in the literature. The performance of the different algorithms is compared under NS-2 simulations. Our results also provide theoretical explanation to the inconsistency of performance improvement by using parallel connections (parallel connections sometimes do not outperform a single connection) observed in some measurement studies.

PrePrint: An Identity-Based Security System For User Privacy in Vehicular Ad Hoc Networks

Vehicular Ad Hoc Network (VANET) can offer various services and benefits to users and thus deserves deployment effort. Attacking and misusing such network could cause destructive consequences. It is therefore necessary to integrate security requirements into the design of VANETs and defend VANET systems against misbehavior, in order to ensure correct and smooth operations of the network. In this paper, we propose a security system for VANETs to achieve privacy desired by vehicles and traceability required by law enforcement authorities, in addition to satisfying fundamental security requirements including authentication, non-repudiation, message integrity and confidentiality. In addition, we propose a privacy-preserving defense technique for network authorities to handle misbehavior in VANET access, considering the challenge that privacy provides avenue for misbehavior. The proposed system employs an identity-based cryptosystem where certificates are not needed for authentication. We show the fulfillment and feasibility of our system with respect to the security goals and efficiency.

PrePrint: A Markovian Approach to Multi-Path Data Transfer in Overlay Networks

The use of multi-path routing in overlay networks is a promising solution to improve performance and availability of Internet applications, without the replacemenet of the existing TCP/IP infrastructure. In this paper, we propose an approach to distribute data over multiple overlay paths that is able to improve Quality of Service (QoS) metrics, such as the data transfer time, loss, and throughput. By using the Imbedded Markov Chain technique, we demonstrate that the system under analysis, observed at specific instants, possesses the Markov property. We therefore cast the data distribution problem into the Markov Decision Process (MDP) framework, and design a computationally efficient algorithm named Online Policy Iteration (OPI), to solve the optimization problem on the fly. The proposed approach is applied to the problem of multi-path data distribution in various wired/wireless network scenarios, with the objective of minimizing the data transfer time as well as the delay and losses. Through both intensive ns-2 simulations with data collected from real heterogeneous networks and experiments over real networks, we show the superior performance of the proposed traffic control mechanism in comparison with two classical schemes, that are Weighted Round Robin and Join the Shortest Queue.

PrePrint: Dynamic Data Reallocation in Hybrid Disk Arrays

Current disk arrays consist purely of hard disk drives, which normally provide huge storage capacities with low-cost and high-throughput for data-intensive applications. Nevertheless, they have some inherent disadvantages such as long access latencies and energy-inefficiency due to their build-in mechanical mechanisms. Flash-memory based solid state disks, on the other hand, although currently more expensive and inadequate in write cycles, offer much faster random read accesses and are much more robust and energy efficient. To combine the complementary merits of hard disks and flash disks, in this paper we propose a hybrid disk array architecture named HIT (hybrid disk storage) for data-intensive applications. Next, a dynamic data redistribution strategy called PEARL (performance, energy, and reliability balanced), which can periodically redistribute data between flash disks and hard disks to adapt to the changing data access patterns, is developed on top of the HIT architecture. Comprehensive simulations using real-life traces demonstrate that compared with existing data placement techniques, PEARL exhibits its strength in both performance and energy consumption without impairing flash disk reliability.

PrePrint: Minimal Sets of Turns for Breaking Cycles in Graphs Modeling Networks

The problem of preventing deadlocks and livelocks in computer communication networks, in particular, those with wormhole routing is considered. The method to prevent deadlocks is to prohibit certain turns (i.e., the use of certain pairs of connected edges) in the routing process, in such a way that eliminates all cycles in the graph. We propose a new algorithm that constructs a minimal (irreducible) set of turns that breaks all cycles and preserves connectivity of the graph. The algorithm is tree-free and is considerably simpler than earlier cycle-breaking algorithms. We prove its properties and present lower and upper bounds for minimum cardinalities of cycle-breaking connectivity-preserving sets for graphs of general topology as well as for planar graphs. In particular, the algorithm guarantees that not more than 1/3 of all turns in the network become prohibited. We also present experimental results on the fraction of prohibited turns, the distance dilation, as well as on the message delivery times and saturation loads for the proposed algorithm in comparison with known tree-based algorithms. The proposed algorithm outperforms substantially the tree-based algorithms in all characteristics considered.

PrePrint: Traffic Management in Sensor Networks with a Mobile Sink

The imminent growth of user-centric, pervasive sensing environments promotes sink mobility in an increasing number of event-based, sensor network applications including rescue missions, intrusion detection and smart buildings. In these settings, one of the most critical challenges toward supporting quality of service, is effective distributed congestion avoidance. Congestion control techniques have been proposed in sensor networks mostly in the context of a static sink. In our work, we study the problem of traffic management in the context of sensor networks with a mobile sink. Under sink mobility, various new challenges arise that need to be effectively addressed. Adaptation to sink mobility requires agile as well as effective load estimation techniques. In addition, unlike static networks, path reliability often fluctuates due to path reconfigurations. Thus, injecting traffic during transient periods of poor path quality might wastefully detain network resources. In this work we first study the effect of sink mobility on traffic load in sensor networks. We then propose adaptive routing as well as load estimation techniques that effectively adapt to sink relocations. A novel aspect of our approach is that it jointly considers the network load as well as path quality variations to facilitate intelligent, mobility-adaptive rate regulation at the sources. We provide a thorough study of the trade-offs induced due to persistent path quality variations and conduct extensive real MICA2-based testbed experiments to study the performance of the sensor network under sink mobility.

PrePrint: Resource Scheduling in Multihop Wireless Networks Using Directional Antennas

A continued increase in the speed and capacities of computing devices, combined with our society's growing need for mobile communication capabilities, multi-hop wireless networks, such as Wireless Mesh Networks (WMNs), have gained a lot of interest from the research community. Quality of service (QoS) provisioning in these networks is an essential component that is needed to support multimedia and real-time applications. On the other hand, directional antenna technology provides the capability for considerable increases in spatial reuse, which is essential in the wireless medium. In this paper, a bandwidth reservation protocol for QoS routing in TDMA-based MWNs using directional antennas is presented. The routing algorithm allows a source node to reserve a path to a particular destination with the needed bandwidth, which is represented by the number of slots in the data phase of the TDMA frame. Further optimizations to improve the efficiency and resource utilization of the network are provided.

PrePrint: A Locally-Adjustable Planar Structure for Adaptive Topology Control in Wireless Ad Hoc Networks

In wireless ad hoc networks, the constructed topology is preferred to be planar since a planar topology enables guaranteed delivery of packets without a routing table. Previous planar structures are statically constructed for the whole network. However, environmental or network dynamics such as channel status, interference or residual energy will prevent such structures from providing the best service to the network. In this paper, we present a t-adjustable planar structure (TAP) which enables each node to adjust the topology independently via a parameter t and allows nodes to have different path loss exponent. TAP is based on three well-known planar structures: Gabriel Graph, Relative Neighborhood Graph, and Local Minimum Spanning Tree. We show properties of TAP by proof or simulation: (1) It preserves connectivity; (2) It is planar, sparse, and symmetric; (3) It preserves all minimum energy path when t = 1 for all nodes; (4) The average transmission power, interference, and node degree decrease as t increases and the maximum node degree is bounded by 6 when t = 3 for all nodes.

PrePrint: Secure Synchronization of Periodic Updates in Ad Hoc Networks

We present techniques for synchronizing nodes that periodically broadcast content and presence updates to co-located nodes over an ad-hoc network, where nodes may exhibit Byzantine malicious behavior. Instead of aligning duty cycles, our algorithms synchronize the periodic transmissions of nodes. This allows nodes to save battery power by switching off their network cards without missing updates from their neighbors. We propose several novel attack classes and show that they are able to disrupt synchronization even when launched by a single attacker. Finally, we devise a rating based algorithm (RBA) that rates neighbors based on the consistency of their behavior. By favoring well-behaved nodes in the synchronization process, we show that RBA quickly stabilizes the synchronization process and reduces the number of lost updates by 85%. Our evaluation also shows that all our algorithms are computationally efficient and, for the setup considered, extend the device lifetime by 30% over an always-on Wi-Fi scenario.

PrePrint: Flexible Cache Consistency Maintenance over Wireless Ad Hoc Networks

One of the major applications of wireless ad hoc networks is to extend the Internet coverage and support pervasive and efficient data dissemination and sharing. To reduce data access cost and delay, caching has been widely used as an important technique. The efficiency of data access in caching systems largely depends on the cost for maintaining cache consistency, which can be high in wireless ad hoc networks due to network dynamism. Therefore, to make better tradeoff between cache consistency and the cost incurred, it would be highly desirable to provide users the flexibility in specifying consistency requirements for their applications. In this paper, we propose a general consistency model called Probabilistic Delta Consistency (PDC), which integrates the flexibility granted by existing consistency models, covering them as special cases. We also propose the Flexible Combination of Push and Pull (FCPP) algorithm which satisfies user-specified consistency requirements under the PDC model. The analytical model of FCPP is used to derive the balance of minimizing the consistency maintenance cost and ensuring the specified consistency requirement. Extensive simulations are conducted to evaluate whether FCPP can satisfy arbitrarily specified consistency requirements, and whether FCPP works cost-effectively in dynamic wireless ad hoc networks. The evaluation results show that FCPP can adaptively tune itself to satisfy various user-specified consistency requirements. Moreover, it can save the traffic cost by up to 50% and reduce the query delay by up to 40%, compared with the widely-used Pull with TTR algorithm.

PrePrint: Incentivized Peer-Assisted Streaming for On-Demand Services

As an efficient distribution mechanism, Peer-to-Peer (P2P) technology has become a tremendously attractive solution to offload servers in large-scale video streaming applications. However, in providing on-demand asynchronous streaming services, P2P streaming design faces two major challenges: how to schedule efficient video sharing between peers with asynchronous playback progresses? how to provide incentives for peers to contribute their resources to achieve a high level of system-wide Quality-of-Experience (QoE)? In this paper, we present iPASS, a novel mesh-based P2P VoD system, to address these challenges. Specifically, iPASS adopts a dynamic buffering-progress-based peering strategy to achieve high peer bandwidth utilization with low system maintenance cost. To provide incentives for peer uploading, iPASS employs a differentiated pre-fetching design that enables peers with higher contribution pre-fetch content at higher speed. A distributed adaptive taxation algorithm is developed to balance the system-wide QoE and service differentiations among heterogeneous peers. To assess the performance of iPASS, we built a detailed packet-level P2P VoD simulator and conducted extensive simulations. It was demonstrated that iPASS can completely offload server when the average peer upload bandwidth is more than 1.2 times the streaming rate. Furthermore, we showed that the distributed incentive algorithm motivates peers to contribute and collaboratively achieve a high level of system wide QoE.

PrePrint: Improving Reliability for Application-Layer Multicast Overlays

Reliability of tree-like multicast overlays caused by nodes’ abrupt failures is considered as one of the major problems for the Internet application-layer media streaming service [1]. In this paper, we address this problem by designing a distributed and light-weighted protocol named the instantaneous reliability oriented protocol (IRP). Unlike most of existing empirical solutions, we first define the overlay reliability problem formally, and propose a protocol containing a node joining algorithm (IRP-Join), a node preemption algorithm (IRP-Preempt), and a node switching algorithm (IRP-Switch) for reactively constructing and repairing the overlay, as well as proactively maintaining the overlay. With the formal problem presentation, we set up a paradigm for solving the overlay reliability problem by theoretically proving the effectiveness of our algorithms. Moreover, by comparing IRP with existing solutions via simulation-based experiments and real-world deployment, we show that IRP achieves a better reliability, while incurs fewer structure adjustments on the multicast overlay, thus providing a superior overall performance.

PrePrint: An Analytical Approach to Optimizing Parallel Image Registration/Retrieval

Image-content queries or image registration algorithms typically have very high computational requirements. In this paper we address the problem of minimizing the total execution time of data-parallel image-content query algorithms on heterogeneous platforms. The model we use to capture the inner workings of these algorithms is comprehensive enough to incorporate not only the communication overheads, both distribution and result collection, but also the presence of local data caches that could exist as a result of previous queries. The problem is solved under all possible computation and communication configurations, including single- and multiple-port communications and block- or stream-type tasks. Our analysis, either, yields closed-form solutions to the partitioning problem, or, formulates the problem in a fashion that allows the use of linear programming tools towards this end. The latter are used for solving the multi-installment data distribution approaches, that tend to utilize the computational resources more efficiently. Additionally, we address the issue of getting a close-to-optimum sequence of load distribution/result collection operations for single-port communications. Based on our analytical results, a thorough simulation and experimental study is performed, yielding substantial design guidelines for implementation strategies.

PrePrint: From an Asynchronous Intermittent Rotating Star to a Leader

Considering an asynchronous system made up of n processes and where up to t of them can crash, finding the weakest assumption that such a system has to satisfy for a common leader to be eventually elected is one of the holy grail quests of fault-tolerant asynchronous computing. This paper has two contributions. It first introduces an additional assumption that allows to elect an eventual leader in all the runs that satisfy that assumption. That assumption is captured by the notion of asynchronous intermittent rotating t-star. The second contribution of the paper is an algorithm that eventually elects a common leader in the systems that satisfy the asynchronous intermittent rotating t-star assumption. That algorithm enjoys, among others, two noteworthy properties. Firstly, from a design point of view, it is simple. Secondly, from a cost point of view, only the pulse numbers increase without bound.

PrePrint: Representation of a Stochastic Traffic Bound

This paper presents a theoretical representation of a stochastic traffic bound (σ’,ρ’) that consists of two items, the burstiness bound σ’ and the bound of long-term average rate ρ’. The novelty of the suggested representation is that the burstiness bound and the bound of long-term average rate are separately connected to the fractal dimension D that is the measure of the local self-similarity together with the small-scale factor r and the Hurst parameter H that is the measure of the long-range dependence (LRD) together with the large-scale factor a of traffic. More precisely, we obtain σ’=r^(2D-5)σ and ρ’=a^(-H) ρ, where σ is the conventional bound of burstiness, and ρ the conventional bound of long-term average rate, respectively. Thus, the present bound (σ’, ρ’) takes the conventional bound, saying (σ,ρ), as a special case when r = 1 and a = 1. Hence, the proposed representation provides us with a flexible way to tighten a traffic bound. Since we study the stochastically bounded modeling of traffic by taking into account the parameters in stochastic modeling, namely, D, H, r, and a, as well as the parameters in the deterministic modeling of traffic, i.e., σ and ρ, a new outlook regarding the stochastically bounded modeling of traffic is revealed. In addition, we open a problem to estimate r and a with respect to the possible applications of the proposed bound to the practice.

Presented By:

NEC

Ads by Pheedo

PrePrint: Self-Disciplinary Worms and Countermeasures: Modeling and Analysis

In this paper, we address issues related to the modeling, analysis, and countermeasures of worm attacks on the Internet. Most previous work assumed that a worm always propagates itself at the highest possible speed. Some newly developed worms (e.g., "Atak" worm) contradict this assumption by deliberately reducing the propagation speed in order to avoid detection. As such, we study a new class of worms, referred to as self-disciplinary worms. These worms adapt their propagation patterns in order to reduce the probability of detection, and to eventually infect more computers. We demonstrate that existing worm detection schemes based on traffic volume and variance cannot effectively defend against these self-disciplinary worms. To develop proper countermeasures, we introduce a game-theoretic formulation to model the interaction between the worm propagator and the defender. We show that an effective integration of multiple countermeasure schemes (e.g., worm detection and forensics analysis) is critical for defending against self-disciplinary worms. We propose different integrated schemes for fighting different self-disciplinary worms, and evaluate their performance via real-world traffic data.

PrePrint: A Near-Optimal Algorithm Attacking the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks

In an unstructured peer-to-peer (P2P) network (e.g., Gnutella), participating peers choose their neighbors randomly such that the resultant P2P network mismatches its underlying physical network, resulting in the lengthy communication between the peers and redundant network traffics generated in the underlying network. Previous solutions to the topology-mismatch problem in the literature either have no performance guarantees or are far from the optimum. In this paper, we propose a novel topology-matching algorithm based on the Metropolis-Hastings method. Our proposal is guided by our insight analytical model and is close to the optimal design. Specifically, we show that our proposal constructs an unstructured P2P network in which a broadcast message, originated by any node $v$, reaches any other node $u$ by taking approximately the only physical end-to-end delay between $v$ and $u$. In addition, our design guarantees the exponential broadcast scope. We verify our solution through extensive simulations, and show that our proposal considerably outperforms state-of-the-art solutions.

PrePrint: An ISP-Friendly File Distribution Protocol: Analysis, Design and Implementation

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 "{\em 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 "{\em black-hole}" security attack. This paper sheds light on the merits and design direction of ISP-friendly content distribution protocols.

PrePrint: Dealing with Transient Faults in the Interconnection Network of CMPs at the Cache Coherence Level

The importance of transient faults is predicted to grow due to current technology trends of increased scale of integration. One of the components that will be significantly affected by transient faults is the interconnection network of CMPs. To deal efficiently with these faults and differently from other authors, we propose to use fault-tolerant cache coherence protocols that ensure the correct execution of programs when not all messages are correctly delivered. We describe the extensions made to a directory-based cache coherence protocol to provide fault tolerance and provide a modified set of token counting rules which are useful to design fault-tolerant token-based cache coherence protocols. We compare the directory-based fault-tolerant protocol with a token-based fault-tolerant one. We also show how to adjust the fault tolerance parameters to achieve the desired level of fault tolerance and measure the overhead achieved to be able to support very high fault rates. Simulation results using a set of scientific, multimedia and commercial applications show that the fault tolerance measures have virtually no impact on execution time with respect to a non fault-tolerant protocol. Additionally, our protocols can support very high rates of transient faults (including bursts) at the cost of slightly increased network traffic.

PrePrint: Detecting Application Denial-of-Service Attacks: A Group Testing Based Approach

Application DoS attack, which aims at disrupting application service rather than depleting the network resource, has emerged as a larger threat to network services, compared to the classic DoS attack. Owing to its high similarity to legitimate traffic and much lower launching overhead than classic DDoS attack, this new assault type cannot be efficiently detected or prevented by existing detection solutions. To identify application DoS attack, we propose a novel group testing(GT) based approach deployed on back-end servers, which not only offers a theoretical method to obtain short detection delay and low false positive/negative rate, but also provides an underlying framework against general network attacks. More specifically, we first extend classic GT model with size constraints for practice purposes, then re-distribute the client service requests to multiple virtual servers embedded within each back-end server machine, according to specific testing matrices. Base on this framework, we propose a 2-mode detection mechanism using some dynamic thresholds to efficiently identify the attackers. The focus of this work lies in the detection algorithms proposed and the corresponding theoretical complexity analysis. We also provide preliminary simulation results regarding the efficiency and practicability of this new scheme. Further discussions over implementation issues and performance enhancements are also appended to show its great potentials.

PrePrint: Correlation-Based Traffic Analysis Attacks on Anonymity Networks

In this paper, we address issues related to flow correlation attacks and the corresponding countermeasures 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 a mix with any known batching strategy may fail against flow correlation attacks allowing the adversary to reconstruct the path used by a flow. We also investigate methods that can effectively counter flow-correlation and other timing attacks. The empirical results provided in this paper give an indication to designers of Mix networks about appropriate configurations and alternative mechanisms to be used to counter flow correlation attacks.

PrePrint: Snoogle: A Search Engine for Pervasive Environments

Embedding small devices into everyday objects like toasters and coffee mugs creates a wireless network of objects. These embedded devices can contain a description of the under-lying objects, or other user defined information. In this paper, we present Snoogle, a search engine for such a network. A user can query Snoogle to find a particular mobile object, or a list of objects that fit the description. Snoogle uses information retrieval techniques to index information and process user queries, and Bloom filters to reduce communication overhead. Security and privacy protections are also engineered into Snoogle to protect sensitive information. We have implemented a prototype of Snoogle using off-the-shelf sensor motes, and conducted extensive experiments to evaluate the system performance.

PrePrint: A Hypergraph Approach to Linear Network Coding in Multicast Networks

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. A typical scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose an approach to transforming the linear coding problem into a graph theory problem. By utilizing hypergraphs, we model the linear codes by constructing a pseudo-dual graph of the multicast network. Then a valid linear code is equivalent to a cover in the pseudo-dual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, we propose several preprocessing algorithms to further reduce the computation time required by the iterative refinements by reducing the graph size before transformation. An important contribution of this work is that the proposed approach can be readily extended to solve many minimal network coding problems. By assigning different weights to edges, minimal network coding problems are reduced to the shortest path problems in the pseudo-dual graph. Our simulation results show that the proposed algorithms can reduce the computation time by about 40-50% in a midium size multicast network, and the throughput of the system with network coding is 25% higher than that with the traditional approach of multiple multicast trees.